From nobody Sat May 18 07:09:04 2024 Delivered-To: importer@patchew.org Authentication-Results: mx.zohomail.com; dkim=fail; spf=pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org; dmarc=fail(p=none dis=none) header.from=gmail.com ARC-Seal: i=1; a=rsa-sha256; t=1623125369; cv=none; d=zohomail.com; s=zohoarc; b=h/ksb/G3Hn/Ymz/nHNFd6xsyayRQVcIQtZGwH5fK+lVsKBiZHwAa0IWOa6qJq9HqnAaVpW/wKFno4NjfRxJr8syay+vSCRwfPtT1KG8LVnAhMl+MpgLhp3TUnYGE/7VPsdftPBa8amUys3Rdc7+xHDEtk+XRAqWxBlkZ6Uh8Fv8= ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=zohomail.com; s=zohoarc; t=1623125369; h=Content-Type:Content-Transfer-Encoding:Cc:Date:From:In-Reply-To:List-Subscribe:List-Post:List-Id:List-Archive:List-Help:List-Unsubscribe:MIME-Version:Message-ID:References:Sender:Subject:To; bh=36oKeZ9qVXLT1pntDuTE8MGk4raH2gBouPHQcv/dO34=; b=LK9c2/AdoEn7oIizmPpDnZlJcKvDUhkSroRimOWiPyfu49mtVnVkWiPN4oQK1ILtmXd/3UGd+nIHD2HkQ8yi4UevWOp2NdzHpKD8oQG8sjiHKuVeAV1JoufEbPVQ6pc1bEi5s4oGEi4FE7iHCix1B4g5iCvCrvgcZ8aRzMJFZ5c= ARC-Authentication-Results: i=1; mx.zohomail.com; dkim=fail; spf=pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org; dmarc=fail header.from= (p=none dis=none) header.from= Return-Path: Received: from lists.gnu.org (lists.gnu.org [209.51.188.17]) by mx.zohomail.com with SMTPS id 162312536937160.6656537706981; Mon, 7 Jun 2021 21:09:29 -0700 (PDT) Received: from localhost ([::1]:37790 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1lqT3P-0006Qa-3D for importer@patchew.org; Tue, 08 Jun 2021 00:09:27 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:48734) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1lqT2A-0003p6-WE for qemu-devel@nongnu.org; Tue, 08 Jun 2021 00:08:11 -0400 Received: from mail-wm1-x329.google.com ([2a00:1450:4864:20::329]:34535) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1lqT29-0008LI-DN for qemu-devel@nongnu.org; Tue, 08 Jun 2021 00:08:10 -0400 Received: by mail-wm1-x329.google.com with SMTP id u5-20020a7bc0450000b02901480e40338bso827771wmc.1 for ; Mon, 07 Jun 2021 21:08:09 -0700 (PDT) Received: from localhost.localdomain ([197.61.123.212]) by smtp.gmail.com with ESMTPSA id y189sm16862008wmy.25.2021.06.07.21.08.06 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 07 Jun 2021 21:08:07 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=36oKeZ9qVXLT1pntDuTE8MGk4raH2gBouPHQcv/dO34=; b=eKaeglgEYxt4DaO7jjobQqoyYuv276p0KGc2TmIROeAfihY7YoSxG9DTdLi9ck3QpS HUz+0zzouJAfk2wT6/bxSkrWmtneZHkDsFtVvHIieD2YPR6tIvj9/y/Pkg98LxKPFGG9 Kc2aDMbFT56hIwwWDQXF9NEfT2hb94opuLa0bp/H5ThQB2sKCNVdZzhZJO8g8vBPLWZb 1XrU0RFF9QXsVs9rp+MIMtn0qpUMzddZccEXY6tIRtpSIG5u0/h2pybgqXQI6XDaX1Tm RHvYoGwvcX+IkPvbXTATIDkzZZXZ3MSQlpm4QWo8e/nzKleBXI5xTUJOkcIU1iLnQh8e ugAA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=36oKeZ9qVXLT1pntDuTE8MGk4raH2gBouPHQcv/dO34=; b=VpgNbjC3V0Guq61tV902qiSeH/JpRSeSac1976IP5CV8PGSObNVR7qY81n6Ml6i0D5 iL4Y/UJ+8LuwZmoSLetI+3v+pGNpN2YqK3alLE/vjNSFTNmWuhpplSsfK+MQ/u1rJPXI oB0rbMBl6Y/MxAY5MA1S7QZbSz6a/z3YPZKQl7z+FOg3q56uZagWaFsn7kLp4TpluaB0 7RonpMLvKxSuUV6agwzz0U4rM6ID8N7dVsLn8hVFo841cj76ZSjf26rptFiUrk3uAogH TMkpdjk8mK4r5vgoP2v2eQS/th8Nfuqs5mfCc2rM75OctllRx8byn99DWRoEhe9MXKeS VGoA== X-Gm-Message-State: AOAM530aCZCsprCMB/96XWKVyA6b4RYEI+3YywPIossDwW3BoO4iC/gR W5CcXhIHv2NFjUI5ZOIA1vhBOZ8wtwuKkA== X-Google-Smtp-Source: ABdhPJwuRvQFwBpUv9+Ucf+U4Jp2UaEzc8vOJU+mkgivBUGNGa0hbtWVI81WJOR2FsLauCv58JA0PQ== X-Received: by 2002:a1c:7508:: with SMTP id o8mr1958900wmc.70.1623125287778; Mon, 07 Jun 2021 21:08:07 -0700 (PDT) From: Mahmoud Mandour To: qemu-devel@nongnu.org Subject: [RFC PATCH v3 1/4] plugins/api: expose symbol lookup to plugins Date: Tue, 8 Jun 2021 06:05:29 +0200 Message-Id: <20210608040532.56449-2-ma.mandourr@gmail.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20210608040532.56449-1-ma.mandourr@gmail.com> References: <20210608040532.56449-1-ma.mandourr@gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable Received-SPF: pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) client-ip=209.51.188.17; envelope-from=qemu-devel-bounces+importer=patchew.org@nongnu.org; helo=lists.gnu.org; Received-SPF: pass client-ip=2a00:1450:4864:20::329; envelope-from=ma.mandourr@gmail.com; helo=mail-wm1-x329.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, FREEMAIL_FROM=0.001, 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.23 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: Mahmoud Mandour , cota@braap.org, =?UTF-8?q?Alex=20Benn=C3=A9e?= Errors-To: qemu-devel-bounces+importer=patchew.org@nongnu.org Sender: "Qemu-devel" X-ZohoMail-DKIM: fail (Header signature does not verify) From: Alex Benn=C3=A9e This is a quality of life helper for plugins so they don't need to re-implement symbol lookup when dumping an address. The strings are constant so don't need to be duplicated. One minor tweak is to return NULL instead of a zero length string to show lookup failed. Signed-off-by: Alex Benn=C3=A9e Message-Id: <20210601145824.3849-1-alex.bennee@linaro.org> Signed-off-by: Mahmoud Mandour --- include/qemu/qemu-plugin.h | 9 +++++++++ plugins/api.c | 6 ++++++ 2 files changed, 15 insertions(+) diff --git a/include/qemu/qemu-plugin.h b/include/qemu/qemu-plugin.h index 97cdfd7761..dc3496f36c 100644 --- a/include/qemu/qemu-plugin.h +++ b/include/qemu/qemu-plugin.h @@ -525,6 +525,15 @@ qemu_plugin_register_vcpu_syscall_ret_cb(qemu_plugin_i= d_t id, =20 char *qemu_plugin_insn_disas(const struct qemu_plugin_insn *insn); =20 +/** + * qemu_plugin_insn_symbol() - best effort symbol lookup + * @insn: instruction reference + * + * Return a static string referring to the symbol. This is dependent + * on the binary QEMU is running having provided a symbol table. + */ +const char *qemu_plugin_insn_symbol(const struct qemu_plugin_insn *insn); + /** * qemu_plugin_vcpu_for_each() - iterate over the existing vCPU * @id: plugin ID diff --git a/plugins/api.c b/plugins/api.c index 817c9b6b69..332e2c60e2 100644 --- a/plugins/api.c +++ b/plugins/api.c @@ -233,6 +233,12 @@ char *qemu_plugin_insn_disas(const struct qemu_plugin_= insn *insn) return plugin_disas(cpu, insn->vaddr, insn->data->len); } =20 +const char *qemu_plugin_insn_symbol(const struct qemu_plugin_insn *insn) +{ + const char *sym =3D lookup_symbol(insn->vaddr); + return sym[0] !=3D 0 ? sym : NULL; +} + /* * The memory queries allow the plugin to query information about a * memory access. --=20 2.25.1 From nobody Sat May 18 07:09:04 2024 Delivered-To: importer@patchew.org Authentication-Results: mx.zohomail.com; dkim=fail; spf=pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org; dmarc=fail(p=none dis=none) header.from=gmail.com ARC-Seal: i=1; a=rsa-sha256; t=1623125370; cv=none; d=zohomail.com; s=zohoarc; b=MSd0A5eaKTGpQ1bvLOa7oE4mqkM930PRQLdvn9I7bdbb0l0p2EMEUjbcxcBuEfmi1jwA53kDo0iPSE/D3UjmmmJKyWXBLFWY5DdOgwoQ0BcGbGpYrxCtxy6RYNkiChADmMKiA/i9JFlVC9Npxm/Fs56K+O6JANU6FyYIxhWdokI= ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=zohomail.com; s=zohoarc; t=1623125370; h=Content-Transfer-Encoding:Cc:Date:From:In-Reply-To:List-Subscribe:List-Post:List-Id:List-Archive:List-Help:List-Unsubscribe:MIME-Version:Message-ID:References:Sender:Subject:To; bh=1I2CE71tnr4W36avsXm1UTgdaLBFwCxU4cDRslNiU+M=; b=InySPvB+f+yPKZZBcVj69mQXxrSSunoNkmrFuV6q8bR199hAvfwqoiHdaLzMEghsLVvW2XsJQBgDgNvyrMIFKbYz6IMR5RCKh8zHTxW47tA6PJfw6FSw25lfjf2ZgLK2lVCpknJb6Ikn7id1rsqNTdNgRpINccsGnL2jz7y1f9o= ARC-Authentication-Results: i=1; mx.zohomail.com; dkim=fail; spf=pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org; dmarc=fail header.from= (p=none dis=none) header.from= Return-Path: Received: from lists.gnu.org (lists.gnu.org [209.51.188.17]) by mx.zohomail.com with SMTPS id 1623125370769569.2926528041249; Mon, 7 Jun 2021 21:09:30 -0700 (PDT) Received: from localhost ([::1]:37976 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1lqT3R-0006Y5-L1 for importer@patchew.org; Tue, 08 Jun 2021 00:09:29 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:48746) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1lqT2D-0003rJ-7J for qemu-devel@nongnu.org; Tue, 08 Jun 2021 00:08:13 -0400 Received: from mail-wm1-x334.google.com ([2a00:1450:4864:20::334]:35645) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1lqT2A-0008Lv-PD for qemu-devel@nongnu.org; Tue, 08 Jun 2021 00:08:13 -0400 Received: by mail-wm1-x334.google.com with SMTP id k5-20020a05600c1c85b02901affeec3ef8so1011985wms.0 for ; Mon, 07 Jun 2021 21:08:10 -0700 (PDT) Received: from localhost.localdomain ([197.61.123.212]) by smtp.gmail.com with ESMTPSA id y189sm16862008wmy.25.2021.06.07.21.08.08 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 07 Jun 2021 21:08:08 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=1I2CE71tnr4W36avsXm1UTgdaLBFwCxU4cDRslNiU+M=; b=k0jJu/b7utSLBB5fxRuXKI+3oYANnCwFlm87fYiYLkTEc/UzuOJNzFKZ14gevZDypv LK8AkupXEhi3vAuGhhrjJaqgZxRb8bnBMEZ442gK1XMkGh9eDM8jJQXfVLAj06LhYuok /YP/myT9S6+E+xjPptcjic9gb8lGoszFBxFIpepKcnAKyy6kb7cFz2Fz7nPDwB6/Fzdp kKthy3lZkbyTBGLzHSkeAPHa1XQ7e3A5eE2guqlkwTqs8eWLs2sQ2wA7teR/2VYktVQ0 +Y5RF8UEYrPTRiRjDcwSlCnXj2mBsdNw90AmGPw3JmzrO14g3P9kT4Y3rKRBxKS0mRFP Sv0Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=1I2CE71tnr4W36avsXm1UTgdaLBFwCxU4cDRslNiU+M=; b=iv1bpPgYTDjrQ4sRweRgj7nELkp6D83D3We8tDqPPL6OJnaK3gqKfUmWwrR2wTq+vY J0vd6T0qP57eAVx8Medh9+3ksWmnkm0m0LCP0Iqf4gsBxgLjAYV94Juhv1ndAfBzPpte F0/41IybFBxMvvgeLQtYEPQHZ6o4FFNbD6HNB/5QPmjHuHWQQw8nHWenLwIqdFdFBo9+ hYGVhe8JjsNgMQZ0W2mOh/ASX1dCMbR0udH4hk2TR9KRR6WMb+2cGpMHx6heAYMPOO9o kVwj+BR3jdrNw/ym2GS4wdfWGYmcCbL0JPm6aP7zKC4IyRpGo4li38kx1gChGqkxkuQx l+ZQ== X-Gm-Message-State: AOAM532bREdgtoYWHDwOvWPLQSCpuVS/bR5EAVwcSK3AwXSRDHKmohqd /ZOb5R7v1Fe1gTZCV1Ej9yU0NAK0T1vyvg== X-Google-Smtp-Source: ABdhPJyNZ9sBW6/6WuQmkeIgIkvHsNwEgXmXRcjytatRLWKktU7rS52FxIiy/zf41peLH1LqbjoTaw== X-Received: by 2002:a1c:3183:: with SMTP id x125mr1988251wmx.80.1623125288996; Mon, 07 Jun 2021 21:08:08 -0700 (PDT) From: Mahmoud Mandour To: qemu-devel@nongnu.org Subject: [RFC PATCH v3 2/4] plugins: Added a new cache modelling plugin. Date: Tue, 8 Jun 2021 06:05:30 +0200 Message-Id: <20210608040532.56449-3-ma.mandourr@gmail.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20210608040532.56449-1-ma.mandourr@gmail.com> References: <20210608040532.56449-1-ma.mandourr@gmail.com> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Received-SPF: pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) client-ip=209.51.188.17; envelope-from=qemu-devel-bounces+importer=patchew.org@nongnu.org; helo=lists.gnu.org; Received-SPF: pass client-ip=2a00:1450:4864:20::334; envelope-from=ma.mandourr@gmail.com; helo=mail-wm1-x334.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, FREEMAIL_FROM=0.001, 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.23 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: Mahmoud Mandour , cota@braap.org, =?UTF-8?q?Alex=20Benn=C3=A9e?= Errors-To: qemu-devel-bounces+importer=patchew.org@nongnu.org Sender: "Qemu-devel" X-ZohoMail-DKIM: fail (Header signature does not verify) Content-Type: text/plain; charset="utf-8" Added a cache modelling plugin that uses a static configuration used in many of the commercial microprocessors and uses random eviction policy. The purpose of the plugin is to identify the most cache-thrashing instructions for both instruction cache and data cache. Signed-off-by: Mahmoud Mandour --- contrib/plugins/Makefile | 1 + contrib/plugins/cache.c | 423 +++++++++++++++++++++++++++++++++++++++ 2 files changed, 424 insertions(+) create mode 100644 contrib/plugins/cache.c diff --git a/contrib/plugins/Makefile b/contrib/plugins/Makefile index b9d7935e5e..2237b47f8b 100644 --- a/contrib/plugins/Makefile +++ b/contrib/plugins/Makefile @@ -18,6 +18,7 @@ NAMES +=3D hotpages NAMES +=3D howvec NAMES +=3D lockstep NAMES +=3D hwprofile +NAMES +=3D cache =20 SONAMES :=3D $(addsuffix .so,$(addprefix lib,$(NAMES))) =20 diff --git a/contrib/plugins/cache.c b/contrib/plugins/cache.c new file mode 100644 index 0000000000..715e5443b0 --- /dev/null +++ b/contrib/plugins/cache.c @@ -0,0 +1,423 @@ +/* + * Copyright (C) 2021, Mahmoud Mandour + * + * License: GNU GPL, version 2 or later. + * See the COPYING file in the top-level directory. + */ + +#include +#include +#include +#include +#include +#include +#include +#include + +#include + +QEMU_PLUGIN_EXPORT int qemu_plugin_version =3D QEMU_PLUGIN_VERSION; + +static enum qemu_plugin_mem_rw rw =3D QEMU_PLUGIN_MEM_RW; + +static GRand *rng; +static GHashTable *miss_ht; + +static GMutex mtx; + +static int limit; +static bool sys; + +static uint64_t dmem_accesses; +static uint64_t dmisses; + +static uint64_t imem_accesses; +static uint64_t imisses; + +/* + * A CacheSet is a set of cache blocks. A memory block that maps to a set = can be + * put in any of the blocks inside the set. The number of block per set is + * called the associativity (assoc). + * + * Each block contains the the stored tag and a valid bit. Since this is n= ot + * a functional simulator, the data itself is not stored. We only identify + * whether a block is in the cache or not by searching for its tag. + * + * In order to search for memory data in the cache, the set identifier and= tag + * are extracted from the address and the set is probed to see whether a t= ag + * match occur. + * + * An address is logically divided into three portions: The block offset, + * the set number, and the tag. + * + * The set number is used to identify the set in which the block may exist. + * The tag is compared against all the tags of a set to search for a match= . If a + * match is found, then the access is a hit. + */ + +struct CacheBlock { + uint64_t tag; + bool valid; +}; + +struct CacheSet { + struct CacheBlock *blocks; +}; + +struct Cache { + struct CacheSet *sets; + int num_sets; + int cachesize; + int assoc; + int blksize_shift; + uint64_t set_mask; + uint64_t tag_mask; +}; + +struct InsnData { + char *disas_str; + const char *symbol; + uint64_t addr; + uint64_t dmisses; + uint64_t imisses; +}; + +struct Cache *dcache, *icache; + +static int pow_of_two(int num) +{ + g_assert((num & (num - 1)) =3D=3D 0); + int ret =3D 0; + while (num /=3D 2) { + ret++; + } + return ret; +} + +static inline uint64_t extract_tag(struct Cache *cache, uint64_t addr) +{ + return addr & cache->tag_mask; +} + +static inline uint64_t extract_set(struct Cache *cache, uint64_t addr) +{ + return (addr & cache->set_mask) >> cache->blksize_shift; +} + +static struct Cache *cache_init(int blksize, int assoc, int cachesize) +{ + struct Cache *cache; + int i; + uint64_t blk_mask; + + cache =3D g_new(struct Cache, 1); + cache->assoc =3D assoc; + cache->cachesize =3D cachesize; + cache->num_sets =3D cachesize / (blksize * assoc); + cache->sets =3D g_new(struct CacheSet, cache->num_sets); + cache->blksize_shift =3D pow_of_two(blksize); + + for (i =3D 0; i < cache->num_sets; i++) { + cache->sets[i].blocks =3D g_new0(struct CacheBlock, assoc); + } + + blk_mask =3D blksize - 1; + cache->set_mask =3D ((cache->num_sets - 1) << cache->blksize_shift); + cache->tag_mask =3D ~(cache->set_mask | blk_mask); + return cache; +} + +static int get_invalid_block(struct Cache *cache, uint64_t set) +{ + int i; + + for (i =3D 0; i < cache->assoc; i++) { + if (!cache->sets[set].blocks[i].valid) { + return i; + } + } + + return -1; +} + +static int get_replaced_block(struct Cache *cache) +{ + return g_rand_int_range(rng, 0, cache->assoc); +} + +static bool in_cache(struct Cache *cache, uint64_t addr) +{ + int i; + uint64_t tag, set; + + tag =3D extract_tag(cache, addr); + set =3D extract_set(cache, addr); + + for (i =3D 0; i < cache->assoc; i++) { + if (cache->sets[set].blocks[i].tag =3D=3D tag && + cache->sets[set].blocks[i].valid) { + return true; + } + } + + return false; +} + +/** + * access_cache(): Simulate a cache access + * @cache: The cache under simulation + * @addr: The address of the requested memory location + * + * Returns true if the requsted data is hit in the cache and false when mi= ssed. + * The cache is updated on miss for the next access. + */ +static bool access_cache(struct Cache *cache, uint64_t addr) +{ + uint64_t tag, set; + int replaced_blk; + + if (in_cache(cache, addr)) { + return true; + } + + tag =3D extract_tag(cache, addr); + set =3D extract_set(cache, addr); + + replaced_blk =3D get_invalid_block(cache, set); + + if (replaced_blk =3D=3D -1) { + replaced_blk =3D get_replaced_block(cache); + } + + cache->sets[set].blocks[replaced_blk].tag =3D tag; + cache->sets[set].blocks[replaced_blk].valid =3D true; + + return false; +} + +static void vcpu_mem_access(unsigned int cpu_index, qemu_plugin_meminfo_t = info, + uint64_t vaddr, void *userdata) +{ + uint64_t insn_addr; + uint64_t effective_addr; + struct qemu_plugin_hwaddr *hwaddr; + struct InsnData *insn; + + g_mutex_lock(&mtx); + hwaddr =3D qemu_plugin_get_hwaddr(info, vaddr); + if (hwaddr && qemu_plugin_hwaddr_is_io(hwaddr)) { + g_mutex_unlock(&mtx); + return; + } + + insn_addr =3D ((struct InsnData *) userdata)->addr; + effective_addr =3D hwaddr ? qemu_plugin_hwaddr_phys_addr(hwaddr) : vad= dr; + + if (!access_cache(dcache, effective_addr)) { + insn =3D (struct InsnData *) userdata; + insn->dmisses++; + dmisses++; + } + dmem_accesses++; + g_mutex_unlock(&mtx); +} + +static void vcpu_insn_exec(unsigned int vcpu_index, void *userdata) +{ + uint64_t insn_addr; + struct InsnData *insn; + + g_mutex_lock(&mtx); + insn_addr =3D ((struct InsnData *) userdata)->addr; + + if (!access_cache(icache, insn_addr)) { + insn =3D (struct InsnData *) userdata; + insn->imisses++; + imisses++; + } + imem_accesses++; + g_mutex_unlock(&mtx); +} + +static void vcpu_tb_trans(qemu_plugin_id_t id, struct qemu_plugin_tb *tb) +{ + size_t n_insns; + size_t i; + struct InsnData *data; + + n_insns =3D qemu_plugin_tb_n_insns(tb); + for (i =3D 0; i < n_insns; i++) { + struct qemu_plugin_insn *insn =3D qemu_plugin_tb_get_insn(tb, i); + uint64_t effective_addr; + + if (sys) { + effective_addr =3D (uint64_t) qemu_plugin_insn_haddr(insn); + } else { + effective_addr =3D (uint64_t) qemu_plugin_insn_vaddr(insn); + } + + /* + * Instructions might get translated multiple times, we do not cre= ate + * new entries for those instructions. Instead, we fetch the same + * entry from the hash table and register it for the callback agai= n. + */ + data =3D g_hash_table_lookup(miss_ht, GUINT_TO_POINTER(effective_a= ddr)); + if (data =3D=3D NULL) { + data =3D g_new0(struct InsnData, 1); + data->disas_str =3D qemu_plugin_insn_disas(insn); + data->symbol =3D qemu_plugin_insn_symbol(insn); + data->addr =3D effective_addr; + g_hash_table_insert(miss_ht, GUINT_TO_POINTER(effective_addr), + (gpointer) data); + } + + qemu_plugin_register_vcpu_mem_cb(insn, vcpu_mem_access, + QEMU_PLUGIN_CB_NO_REGS, + rw, data); + + qemu_plugin_register_vcpu_insn_exec_cb(insn, vcpu_insn_exec, + QEMU_PLUGIN_CB_NO_REGS, dat= a); + } +} + +static void free_insn(gpointer data) +{ + struct InsnData *insn =3D (struct InsnData *) data; + g_free(insn->disas_str); + g_free(insn); +} + +static void free_cache(struct Cache *cache) +{ + for (int i =3D 0; i < cache->num_sets; i++) { + g_free(cache->sets[i].blocks); + } + + g_free(cache->sets); + g_free(cache); +} + +static int dcmp(gconstpointer a, gconstpointer b) +{ + struct InsnData *insn_a =3D (struct InsnData *) a; + struct InsnData *insn_b =3D (struct InsnData *) b; + + return insn_a->dmisses < insn_b->dmisses ? 1 : -1; +} + +static int icmp(gconstpointer a, gconstpointer b) +{ + struct InsnData *insn_a =3D (struct InsnData *) a; + struct InsnData *insn_b =3D (struct InsnData *) b; + + return insn_a->imisses < insn_b->imisses ? 1 : -1; +} + +static void log_stats() +{ + g_autoptr(GString) rep =3D g_string_new(""); + g_string_append_printf(rep, + "Data accesses: %lu, Misses: %lu\nMiss rate: %lf%%\n\n", + dmem_accesses, + dmisses, + ((double) dmisses / dmem_accesses) * 100.0); + + g_string_append_printf(rep, + "Instruction accesses: %lu, Misses: %lu\nMiss rate: %lf%%\n\n", + imem_accesses, + imisses, + ((double) imisses / imem_accesses) * 100.0); + + qemu_plugin_outs(rep->str); +} + +static void plugin_exit() +{ + GList *curr, *miss_insns; + int i; + struct InsnData *insn; + + g_mutex_lock(&mtx); + + log_stats(); + + miss_insns =3D g_hash_table_get_values(miss_ht); + miss_insns =3D g_list_sort(miss_insns, dcmp); + g_autoptr(GString) rep =3D g_string_new(""); + g_string_append_printf(rep, "%s", "address, data misses, instruction\n= "); + + for (curr =3D miss_insns, i =3D 0; curr && i < limit; i++, curr =3D cu= rr->next) { + insn =3D (struct InsnData *) curr->data; + g_string_append_printf(rep, "0x%" PRIx64, insn->addr); + if (insn->symbol) { + g_string_append_printf(rep, " (%s)", insn->symbol); + } + g_string_append_printf(rep, ", %ld, %s\n", insn->dmisses, + insn->disas_str); + } + + miss_insns =3D g_list_sort(miss_insns, icmp); + g_string_append_printf(rep, "%s", "\naddress, fetch misses, instructio= n\n"); + + for (curr =3D miss_insns, i =3D 0; curr && i < limit; i++, curr =3D cu= rr->next) { + insn =3D (struct InsnData *) curr->data; + g_string_append_printf(rep, "0x%" PRIx64, insn->addr); + if (insn->symbol) { + g_string_append_printf(rep, " (%s)", insn->symbol); + } + g_string_append_printf(rep, ", %ld, %s\n", insn->imisses, + insn->disas_str); + } + + qemu_plugin_outs(rep->str); + + free_cache(dcache); + free_cache(icache); + + g_list_free(miss_insns); + + g_hash_table_destroy(miss_ht); + g_mutex_unlock(&mtx); +} + +QEMU_PLUGIN_EXPORT +int qemu_plugin_install(qemu_plugin_id_t id, const qemu_info_t *info, + int argc, char **argv) +{ + int i; + int iassoc, iblksize, icachesize; + int dassoc, dblksize, dcachesize; + + limit =3D 32; + sys =3D info->system_emulation; + + dassoc =3D 8; + dblksize =3D 64; + dcachesize =3D dblksize * dassoc * 32; + + iassoc =3D 8; + iblksize =3D 64; + icachesize =3D iblksize * iassoc * 32; + + rng =3D g_rand_new(); + + for (i =3D 0; i < argc; i++) { + char *opt =3D argv[i]; + if (g_str_has_prefix(opt, "limit=3D")) { + limit =3D g_ascii_strtoull(opt + 6, NULL, 10); + } else { + fprintf(stderr, "option parsing failed: %s\n", opt); + return -1; + } + } + + dcache =3D cache_init(dblksize, dassoc, dcachesize); + icache =3D cache_init(iblksize, iassoc, icachesize); + + qemu_plugin_register_vcpu_tb_trans_cb(id, vcpu_tb_trans); + qemu_plugin_register_atexit_cb(id, plugin_exit, NULL); + + miss_ht =3D g_hash_table_new_full(NULL, g_direct_equal, NULL, free_ins= n); + + return 0; +} --=20 2.25.1 From nobody Sat May 18 07:09:04 2024 Delivered-To: importer@patchew.org Authentication-Results: mx.zohomail.com; dkim=fail; spf=pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org; dmarc=fail(p=none dis=none) header.from=gmail.com ARC-Seal: i=1; a=rsa-sha256; t=1623125370; cv=none; d=zohomail.com; s=zohoarc; b=Yf0oA+zrRriLYHjF1b4028QQ59qnjOvFWwvfeGvSi35Z614zk+65Pbh5mOmNlNWSSTe4CFUT0n7N+cD501tVDPEbVfOhTgbkY9YlnKwVWj7h/LrGckmmQ8NwDS3KnLhq8JfpsSX01IMKNgIlbo++AgCggzUJkFIcKdBou24XFo0= ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=zohomail.com; s=zohoarc; t=1623125370; h=Content-Transfer-Encoding:Cc:Date:From:In-Reply-To:List-Subscribe:List-Post:List-Id:List-Archive:List-Help:List-Unsubscribe:MIME-Version:Message-ID:References:Sender:Subject:To; bh=RVydF8W/6ZNYBMXe/l8al/gKrABRXvmDJUUWROof7X8=; b=iKbHZmV/hu/GpQYLTmF3F+FQzI5UcpxHdwFosN4T4SvRrMxA33EUmO0aV8s53poyTjuAxVI0xUJ6uLtqAl1pno5Sk+HB53dD86tylREcKtkNfaWTPIYOBlZduHR/KKJcvAb9Wmp4BAXhYqrT6xk5raIWxDabnqlvXSQKldhST2s= ARC-Authentication-Results: i=1; mx.zohomail.com; dkim=fail; spf=pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org; dmarc=fail header.from= (p=none dis=none) header.from= Return-Path: Received: from lists.gnu.org (lists.gnu.org [209.51.188.17]) by mx.zohomail.com with SMTPS id 1623125370537246.30971871385168; Mon, 7 Jun 2021 21:09:30 -0700 (PDT) Received: from localhost ([::1]:38042 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1lqT3R-0006ag-EX for importer@patchew.org; Tue, 08 Jun 2021 00:09:29 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:48768) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1lqT2F-0003tQ-9u for qemu-devel@nongnu.org; Tue, 08 Jun 2021 00:08:15 -0400 Received: from mail-wr1-x435.google.com ([2a00:1450:4864:20::435]:37672) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1lqT2B-0008Mc-Qp for qemu-devel@nongnu.org; Tue, 08 Jun 2021 00:08:15 -0400 Received: by mail-wr1-x435.google.com with SMTP id i94so14852788wri.4 for ; Mon, 07 Jun 2021 21:08:11 -0700 (PDT) Received: from localhost.localdomain ([197.61.123.212]) by smtp.gmail.com with ESMTPSA id y189sm16862008wmy.25.2021.06.07.21.08.09 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 07 Jun 2021 21:08:10 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=RVydF8W/6ZNYBMXe/l8al/gKrABRXvmDJUUWROof7X8=; b=EvDR+mNCh0kHyxqJyLQbtZjKltl6zfxnkmu1ErcSgQyFDgmtKd5+kJFEJySRj4jWh9 0i2QxHAqqOvJ5AZ7d0JdR3mTsqetg+dN3H7JHQKNstQT5rOThQVQ4zvJnIHceWO0dja/ cTMMveT3uo/vGuYfPSoG5r7CbTjdXteBhm4XWA3vl4fY+9OQ7I/29Ca19cvy7hLiUoD9 NHfhANR3utzm3trUfVGnByBTDzMKxaPplKgzUnPm7YlYh8kaynuUf3OzGRrz1fw2PYqg 48mteOowEtUyzsFiKGx+gJJ6E/1tghNYWQTFnz5v23NgHU7H48LMLONPkEdSm7FpK2Bu 0R9g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=RVydF8W/6ZNYBMXe/l8al/gKrABRXvmDJUUWROof7X8=; b=R5n2AKSI377VWTjxMKrFA5tLaNMBrxZ5uKU7g4z4ieIqejkWfjktU65EtC96xPlRPn RJxlUNKMBI6fevM3Yxr5EeHO+JtbxnLoP0eRBPeYnmF+2JZ7/4iaVVzVaMe6x4E44CsK VICZ0u0V6yySy4DJDYJFquCmFpvYDQl7aqwPllDLmLdbFEHftivw7Ut9RK01LbbyAi6H DyNB9ExBwEeUbLt6/haVvR6+XlTV5zK/wJbTNJZeLTxaOw7LL6PTf6UZWmM03pgxlTLI zu675WO+AEn3KhsuZeDBfYpCMy/GHrzlJ2DIa9n7iMtAVP+vQxG5ids+vJRxBMQPNeUY DuLw== X-Gm-Message-State: AOAM5334jzp51GOeUvKhdaAvCpVrCiq5bVSeMgEizKppOePFjsHIL25e r7Sb9dk7t4wO34F0fOM35UOhX42WHIibUw== X-Google-Smtp-Source: ABdhPJxh/JFJanrgKDvHjB0a+dkIHAGqkWSF+iosKsXmepzdM6hXhkzm0z3ywv20InusdHc3rQpVWQ== X-Received: by 2002:adf:c54b:: with SMTP id s11mr20478065wrf.349.1623125290341; Mon, 07 Jun 2021 21:08:10 -0700 (PDT) From: Mahmoud Mandour To: qemu-devel@nongnu.org Subject: [RFC PATCH v3 3/4] plugins/cache: Enabled cache parameterization Date: Tue, 8 Jun 2021 06:05:31 +0200 Message-Id: <20210608040532.56449-4-ma.mandourr@gmail.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20210608040532.56449-1-ma.mandourr@gmail.com> References: <20210608040532.56449-1-ma.mandourr@gmail.com> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Received-SPF: pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) client-ip=209.51.188.17; envelope-from=qemu-devel-bounces+importer=patchew.org@nongnu.org; helo=lists.gnu.org; Received-SPF: pass client-ip=2a00:1450:4864:20::435; envelope-from=ma.mandourr@gmail.com; helo=mail-wr1-x435.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, FREEMAIL_FROM=0.001, 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.23 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: Mahmoud Mandour , cota@braap.org, =?UTF-8?q?Alex=20Benn=C3=A9e?= Errors-To: qemu-devel-bounces+importer=patchew.org@nongnu.org Sender: "Qemu-devel" X-ZohoMail-DKIM: fail (Header signature does not verify) Content-Type: text/plain; charset="utf-8" Made both icache and dcache configurable through plugin arguments. Signed-off-by: Mahmoud Mandour --- contrib/plugins/cache.c | 44 +++++++++++++++++++++++++++++++++++++++-- 1 file changed, 42 insertions(+), 2 deletions(-) diff --git a/contrib/plugins/cache.c b/contrib/plugins/cache.c index 715e5443b0..d8e8c750b6 100644 --- a/contrib/plugins/cache.c +++ b/contrib/plugins/cache.c @@ -104,8 +104,17 @@ static inline uint64_t extract_set(struct Cache *cache= , uint64_t addr) return (addr & cache->set_mask) >> cache->blksize_shift; } =20 +static bool bad_cache_params(int blksize, int assoc, int cachesize) +{ + return (cachesize % blksize) !=3D 0 || (cachesize % (blksize * assoc) = !=3D 0); +} + static struct Cache *cache_init(int blksize, int assoc, int cachesize) { + if (bad_cache_params(blksize, assoc, cachesize)) { + return NULL; + } + struct Cache *cache; int i; uint64_t blk_mask; @@ -403,8 +412,30 @@ int qemu_plugin_install(qemu_plugin_id_t id, const qem= u_info_t *info, =20 for (i =3D 0; i < argc; i++) { char *opt =3D argv[i]; - if (g_str_has_prefix(opt, "limit=3D")) { - limit =3D g_ascii_strtoull(opt + 6, NULL, 10); + if (g_str_has_prefix(opt, "I=3D")) { + gchar **toks =3D g_strsplit(opt + 2, " ", -1); + if (g_strv_length(toks) !=3D 3) { + g_strfreev(toks); + fprintf(stderr, "option parsing failed: %s\n", opt); + return -1; + } + icachesize =3D g_ascii_strtoull(toks[0], NULL, 10); + iassoc =3D g_ascii_strtoull(toks[1], NULL, 10); + iblksize =3D g_ascii_strtoull(toks[2], NULL, 10); + g_strfreev(toks); + } else if (g_str_has_prefix(opt, "D=3D")) { + gchar **toks =3D g_strsplit(opt + 2, " ", -1); + if (g_strv_length(toks) !=3D 3) { + g_strfreev(toks); + fprintf(stderr, "option parsing failed: %s\n", opt); + return -1; + } + dcachesize =3D g_ascii_strtoull(toks[0], NULL, 10); + dassoc =3D g_ascii_strtoull(toks[1], NULL, 10); + dblksize =3D g_ascii_strtoull(toks[2], NULL, 10); + g_strfreev(toks); + } else if (g_str_has_prefix(opt, "limit=3D")) { + limit =3D g_ascii_strtoll(opt + 6, NULL, 10); } else { fprintf(stderr, "option parsing failed: %s\n", opt); return -1; @@ -412,7 +443,16 @@ int qemu_plugin_install(qemu_plugin_id_t id, const qem= u_info_t *info, } =20 dcache =3D cache_init(dblksize, dassoc, dcachesize); + if (!dcache) { + fprintf(stderr, "dcache cannot be constructed from given parameter= s\n"); + return -1; + } + icache =3D cache_init(iblksize, iassoc, icachesize); + if (!icache) { + fprintf(stderr, "icache cannot be constructed from given parameter= s\n"); + return -1; + } =20 qemu_plugin_register_vcpu_tb_trans_cb(id, vcpu_tb_trans); qemu_plugin_register_atexit_cb(id, plugin_exit, NULL); --=20 2.25.1 From nobody Sat May 18 07:09:04 2024 Delivered-To: importer@patchew.org Authentication-Results: mx.zohomail.com; dkim=fail; spf=pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org; dmarc=fail(p=none dis=none) header.from=gmail.com ARC-Seal: i=1; a=rsa-sha256; t=1623125450; cv=none; d=zohomail.com; s=zohoarc; b=E4vFXGFBtKunwoJCC0RlYOTNCH0nwWVxJtB7ITgy+SAWUWfnrdcE+Ge+JAqrBqp/IOnnXgV8xk8W+1JFIp6+YnHIdSTtbCn/GHH2OnEmkTA2m9ho33x2NmnL0A5Lxvux6os7/6oEVrhYfYpFp3tslQronxT9RBFVInZ6/15H8bI= ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=zohomail.com; s=zohoarc; t=1623125450; h=Content-Transfer-Encoding:Cc:Date:From:In-Reply-To:List-Subscribe:List-Post:List-Id:List-Archive:List-Help:List-Unsubscribe:MIME-Version:Message-ID:References:Sender:Subject:To; bh=2WAk/Hd46RzXhp4Qf1TvKjU7cXGKlg3VjTVfixKRX+0=; b=R8w9/UxNY8aD+WgD/xBjBYiPce77eYEj8UPfeScsRBUZYcdvkaIjI2GJD+i7L2FmRYEqLICkrHjzys3vHwkwieHJb2k7e4sHVAG0Uxw647Aqco49PS5mGIbAgulEtavWLmYFHB1oVQFskW0NepLaAI4nnZfCPHRIsdc7Gl43rqc= ARC-Authentication-Results: i=1; mx.zohomail.com; dkim=fail; spf=pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org; dmarc=fail header.from= (p=none dis=none) header.from= Return-Path: Received: from lists.gnu.org (lists.gnu.org [209.51.188.17]) by mx.zohomail.com with SMTPS id 1623125450433133.8666693148367; Mon, 7 Jun 2021 21:10:50 -0700 (PDT) Received: from localhost ([::1]:43368 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1lqT4j-0001iy-Di for importer@patchew.org; Tue, 08 Jun 2021 00:10:49 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:48778) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1lqT2G-0003vb-0Z for qemu-devel@nongnu.org; Tue, 08 Jun 2021 00:08:16 -0400 Received: from mail-wr1-x436.google.com ([2a00:1450:4864:20::436]:43876) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1lqT2D-0008Mp-9V for qemu-devel@nongnu.org; Tue, 08 Jun 2021 00:08:15 -0400 Received: by mail-wr1-x436.google.com with SMTP id r9so3196178wrz.10 for ; Mon, 07 Jun 2021 21:08:12 -0700 (PDT) Received: from localhost.localdomain ([197.61.123.212]) by smtp.gmail.com with ESMTPSA id y189sm16862008wmy.25.2021.06.07.21.08.10 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 07 Jun 2021 21:08:11 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=2WAk/Hd46RzXhp4Qf1TvKjU7cXGKlg3VjTVfixKRX+0=; b=Mcw3Y2KEE8Pta0cu3M4/Wa1SY8+NPyL1ZPIeVsaAbcyMsB+4vq8mCuTKGYS/Kyo0QO KaEHhPfxtpflMmTR0yR0eDzyEz6xhF963It2hlgkHnSYQpctYykHmpgy4vltWCmxheDe Z+sm9Rd7qY0CKZDA2bpcxjN4rN1oSit1udJhu+v2WJc0+IQZoR2nTk5aI9igEHosf4Cz CpScQKNvwN/YUTGq/ya5c54WEqjmoc8riaS0ls7zzfas0XBKgxCOrUryzjtatY+lpBfF COpYYSJbaJZd4K67+aXZ/tPdxjWdR7U/womfLhcC/LfD8OxNZNYlsYE71kFsMWnqfM+b F0fw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=2WAk/Hd46RzXhp4Qf1TvKjU7cXGKlg3VjTVfixKRX+0=; b=sLYurxWrWkJEHpNC8V5nV3+E33LWZAr3J1L33vuZ+Z1yA/6TBEBZyzi3qZjAbwXHnV W0VdpMSZ7IomraBmVTzveEB73rv7uvHDaUT+4cHiNNkvFA8+SPWIjAcDNc5oTNTgFu6K i1Edp5a/IfBscXMCpbRPyqnz5Oxtm+u+Wrn51u7pSTK8/e5NhGvDz+ch+oEYByIsv1Tb CO2pTLKHw1si2FXT8XBqlmdacsIaQEI3ScVjBrvTiFsRKzDajdJesoXKAVR6TTB3DjC8 6d2SDc70uOEiiUFJNfPNwskqw2DVK0AEJ6k6lnCZOX1EwzfIGCGuSLEFPgsk46RhY7hO 1PEA== X-Gm-Message-State: AOAM532Tp8WGejkuI9GOPamgLqgyE5+ZJwn148XygdyN7EShvNJD+3/h KWtU76OVFnkGkmzkR/hxZDqsaYfLPcogzg== X-Google-Smtp-Source: ABdhPJyQw26AxsWzAFpae9w2lNhZD9CXPElQd8Krr7712FoLyLDkNp0V9whmYBJZx6fLAm4XZWFMHw== X-Received: by 2002:adf:fd06:: with SMTP id e6mr20374563wrr.335.1623125291633; Mon, 07 Jun 2021 21:08:11 -0700 (PDT) From: Mahmoud Mandour To: qemu-devel@nongnu.org Subject: [RFC PATCH v3 4/4] plugins/cache: Added FIFO and LRU eviction policies. Date: Tue, 8 Jun 2021 06:05:32 +0200 Message-Id: <20210608040532.56449-5-ma.mandourr@gmail.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20210608040532.56449-1-ma.mandourr@gmail.com> References: <20210608040532.56449-1-ma.mandourr@gmail.com> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Received-SPF: pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) client-ip=209.51.188.17; envelope-from=qemu-devel-bounces+importer=patchew.org@nongnu.org; helo=lists.gnu.org; Received-SPF: pass client-ip=2a00:1450:4864:20::436; envelope-from=ma.mandourr@gmail.com; helo=mail-wr1-x436.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, FREEMAIL_FROM=0.001, 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.23 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: Mahmoud Mandour , cota@braap.org, =?UTF-8?q?Alex=20Benn=C3=A9e?= Errors-To: qemu-devel-bounces+importer=patchew.org@nongnu.org Sender: "Qemu-devel" X-ZohoMail-DKIM: fail (Header signature does not verify) Content-Type: text/plain; charset="utf-8" Implemented FIFO and LRU eviction policies. Now one of the three eviction policies can be chosen as an argument. On not specifying an argument, LRU is used by default. Signed-off-by: Mahmoud Mandour Reviewed-by: Alex Benn=C3=A9e --- contrib/plugins/cache.c | 205 +++++++++++++++++++++++++++++++++++++--- 1 file changed, 192 insertions(+), 13 deletions(-) diff --git a/contrib/plugins/cache.c b/contrib/plugins/cache.c index d8e8c750b6..be817da5b6 100644 --- a/contrib/plugins/cache.c +++ b/contrib/plugins/cache.c @@ -34,6 +34,14 @@ static uint64_t dmisses; static uint64_t imem_accesses; static uint64_t imisses; =20 +enum EvictionPolicy { + LRU, + FIFO, + RAND, +}; + +enum EvictionPolicy policy; + /* * A CacheSet is a set of cache blocks. A memory block that maps to a set = can be * put in any of the blocks inside the set. The number of block per set is @@ -53,6 +61,8 @@ static uint64_t imisses; * The set number is used to identify the set in which the block may exist. * The tag is compared against all the tags of a set to search for a match= . If a * match is found, then the access is a hit. + * + * The CacheSet also contains bookkeaping information about eviction detai= ls. */ =20 struct CacheBlock { @@ -62,6 +72,9 @@ struct CacheBlock { =20 struct CacheSet { struct CacheBlock *blocks; + uint64_t *lru_priorities; + uint64_t lru_gen_counter; + GQueue *fifo_queue; }; =20 struct Cache { @@ -82,6 +95,12 @@ struct InsnData { uint64_t imisses; }; =20 +void (*update_hit)(struct Cache *cache, int set, int blk); +void (*update_miss)(struct Cache *cache, int set, int blk); + +void (*metadata_init)(struct Cache *cache); +void (*metadata_destroy)(struct Cache *cache); + struct Cache *dcache, *icache; =20 static int pow_of_two(int num) @@ -104,6 +123,103 @@ static inline uint64_t extract_set(struct Cache *cach= e, uint64_t addr) return (addr & cache->set_mask) >> cache->blksize_shift; } =20 +/* + * LRU evection policy: For each set, a generation counter is maintained + * alongside a priority array. + * + * On each set access, the generation counter is incremented. + * + * On a cache hit: The hit-block is assigned the current generation counte= r, + * indicating that it is the most recently used block. + * + * On a cache miss: The block with the least priority is searched and repl= aced + * with the newly-cached block, of which the priority is set to the current + * generation number. + */ + +static void lru_priorities_init(struct Cache *cache) +{ + int i, assoc; + + assoc =3D cache->assoc; + for (i =3D 0; i < cache->num_sets; i++) { + cache->sets[i].lru_priorities =3D g_new0(uint64_t, assoc); + } +} + +static void lru_update_blk(struct Cache *cache, int set_idx, int blk_idx) +{ + struct CacheSet *set =3D &cache->sets[set_idx]; + set->lru_priorities[blk_idx] =3D cache->sets[set_idx].lru_gen_counter; + set->lru_gen_counter++; +} + +static int lru_get_lru_block(struct Cache *cache, int set_idx) +{ + int i, min_idx, min_priority; + + min_priority =3D cache->sets[set_idx].lru_priorities[0]; + min_idx =3D 0; + + for (i =3D 1; i < cache->assoc; i++) { + if (cache->sets[set_idx].lru_priorities[i] < min_priority) { + min_priority =3D cache->sets[set_idx].lru_priorities[i]; + min_idx =3D i; + } + } + return min_idx; +} + +static void lru_priorities_destroy(struct Cache *cache) +{ + int i; + + for (i =3D 0; i < cache->num_sets; i++) { + g_free(cache->sets[i].lru_priorities); + } +} + +/* + * FIFO eviction policy: a FIFO queue is maintained for each CacheSet that + * stores accesses to the cache. + * + * On a compulsory miss: The block index is enqueued to the fifo_queue to + * indicate that it's the latest cached block. + * + * On a conflict miss: The first-in block is removed from the cache and th= e new + * block is put in its place and enqueued to the FIFO queue. + */ + +static void fifo_init(struct Cache *cache) +{ + int i; + + for (i =3D 0; i < cache->num_sets; i++) { + cache->sets[i].fifo_queue =3D g_queue_new(); + } +} + +static int fifo_get_first_block(struct Cache *cache, int set) +{ + GQueue *q =3D cache->sets[set].fifo_queue; + return GPOINTER_TO_INT(g_queue_pop_tail(q)); +} + +static void fifo_update_on_miss(struct Cache *cache, int set, int blk_idx) +{ + GQueue *q =3D cache->sets[set].fifo_queue; + g_queue_push_head(q, GINT_TO_POINTER(blk_idx)); +} + +static void fifo_destroy(struct Cache *cache) +{ + int i; + + for (i =3D 0; i < cache->assoc; i++) { + g_queue_free(cache->sets[i].fifo_queue); + } +} + static bool bad_cache_params(int blksize, int assoc, int cachesize) { return (cachesize % blksize) !=3D 0 || (cachesize % (blksize * assoc) = !=3D 0); @@ -128,11 +244,17 @@ static struct Cache *cache_init(int blksize, int asso= c, int cachesize) =20 for (i =3D 0; i < cache->num_sets; i++) { cache->sets[i].blocks =3D g_new0(struct CacheBlock, assoc); + cache->sets[i].lru_gen_counter =3D 0; } =20 blk_mask =3D blksize - 1; cache->set_mask =3D ((cache->num_sets - 1) << cache->blksize_shift); cache->tag_mask =3D ~(cache->set_mask | blk_mask); + + if (metadata_init) { + metadata_init(cache); + } + return cache; } =20 @@ -149,12 +271,21 @@ static int get_invalid_block(struct Cache *cache, uin= t64_t set) return -1; } =20 -static int get_replaced_block(struct Cache *cache) +static int get_replaced_block(struct Cache *cache, int set) { - return g_rand_int_range(rng, 0, cache->assoc); + switch (policy) { + case RAND: + return g_rand_int_range(rng, 0, cache->assoc); + case LRU: + return lru_get_lru_block(cache, set); + case FIFO: + return fifo_get_first_block(cache, set); + defalut: + g_assert_not_reached(); + } } =20 -static bool in_cache(struct Cache *cache, uint64_t addr) +static int in_cache(struct Cache *cache, uint64_t addr) { int i; uint64_t tag, set; @@ -165,11 +296,11 @@ static bool in_cache(struct Cache *cache, uint64_t ad= dr) for (i =3D 0; i < cache->assoc; i++) { if (cache->sets[set].blocks[i].tag =3D=3D tag && cache->sets[set].blocks[i].valid) { - return true; + return i; } } =20 - return false; + return -1; } =20 /** @@ -178,24 +309,32 @@ static bool in_cache(struct Cache *cache, uint64_t ad= dr) * @addr: The address of the requested memory location * * Returns true if the requsted data is hit in the cache and false when mi= ssed. - * The cache is updated on miss for the next access. + * The cache is then updated for subsequent accesses. */ static bool access_cache(struct Cache *cache, uint64_t addr) { + int hit_blk, replaced_blk; uint64_t tag, set; - int replaced_blk; - - if (in_cache(cache, addr)) { - return true; - } =20 tag =3D extract_tag(cache, addr); set =3D extract_set(cache, addr); =20 + hit_blk =3D in_cache(cache, addr); + if (hit_blk !=3D -1) { + if (update_hit) { + update_hit(cache, set, hit_blk); + } + return true; + } + replaced_blk =3D get_invalid_block(cache, set); =20 if (replaced_blk =3D=3D -1) { - replaced_blk =3D get_replaced_block(cache); + replaced_blk =3D get_replaced_block(cache, set); + } + + if (update_miss) { + update_miss(cache, set, replaced_blk); } =20 cache->sets[set].blocks[replaced_blk].tag =3D tag; @@ -302,6 +441,10 @@ static void free_cache(struct Cache *cache) g_free(cache->sets[i].blocks); } =20 + if (metadata_destroy) { + metadata_destroy(cache); + } + g_free(cache->sets); g_free(cache); } @@ -389,6 +532,28 @@ static void plugin_exit() g_mutex_unlock(&mtx); } =20 +static void policy_init() +{ + switch (policy) { + case LRU: + update_hit =3D lru_update_blk; + update_miss =3D lru_update_blk; + metadata_init =3D lru_priorities_init; + metadata_destroy =3D lru_priorities_destroy; + break; + case FIFO: + update_miss =3D fifo_update_on_miss; + metadata_init =3D fifo_init; + metadata_destroy =3D fifo_destroy; + break; + case RAND: + rng =3D g_rand_new(); + break; + default: + g_assert_not_reached(); + } +} + QEMU_PLUGIN_EXPORT int qemu_plugin_install(qemu_plugin_id_t id, const qemu_info_t *info, int argc, char **argv) @@ -408,7 +573,7 @@ int qemu_plugin_install(qemu_plugin_id_t id, const qemu= _info_t *info, iblksize =3D 64; icachesize =3D iblksize * iassoc * 32; =20 - rng =3D g_rand_new(); + policy =3D LRU; =20 for (i =3D 0; i < argc; i++) { char *opt =3D argv[i]; @@ -436,12 +601,26 @@ int qemu_plugin_install(qemu_plugin_id_t id, const qe= mu_info_t *info, g_strfreev(toks); } else if (g_str_has_prefix(opt, "limit=3D")) { limit =3D g_ascii_strtoll(opt + 6, NULL, 10); + } else if (g_str_has_prefix(opt, "evict=3D")) { + gchar *p =3D opt + 6; + if (g_strcmp0(p, "rand") =3D=3D 0) { + policy =3D RAND; + } else if (g_strcmp0(p, "lru") =3D=3D 0) { + policy =3D LRU; + } else if (g_strcmp0(p, "fifo") =3D=3D 0) { + policy =3D FIFO; + } else { + fprintf(stderr, "invalid eviction policy: %s\n", opt); + return -1; + } } else { fprintf(stderr, "option parsing failed: %s\n", opt); return -1; } } =20 + policy_init(); + dcache =3D cache_init(dblksize, dassoc, dcachesize); if (!dcache) { fprintf(stderr, "dcache cannot be constructed from given parameter= s\n"); --=20 2.25.1