From patchwork Tue Aug 4 09:14:02 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: SeongJae Park X-Patchwork-Id: 11700061 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 06C46913 for ; Tue, 4 Aug 2020 09:15:20 +0000 (UTC) Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by mail.kernel.org (Postfix) with ESMTP id EDACA206DA for ; Tue, 4 Aug 2020 09:15:19 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (1024-bit key) header.d=amazon.com header.i=@amazon.com header.b="BinWGlmR" DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org EDACA206DA Authentication-Results: mail.kernel.org; dmarc=fail (p=quarantine dis=none) header.from=amazon.com Authentication-Results: mail.kernel.org; spf=pass smtp.mailfrom=owner-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix) id 15B768D0137; Tue, 4 Aug 2020 05:15:19 -0400 (EDT) Delivered-To: linux-mm-outgoing@kvack.org Received: by kanga.kvack.org (Postfix, from userid 40) id 10B4A8D0135; Tue, 4 Aug 2020 05:15:19 -0400 (EDT) X-Original-To: int-list-linux-mm@kvack.org X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id F13EB8D0137; Tue, 4 Aug 2020 05:15:18 -0400 (EDT) X-Original-To: linux-mm@kvack.org X-Delivered-To: linux-mm@kvack.org Received: from forelay.hostedemail.com (smtprelay0199.hostedemail.com [216.40.44.199]) by kanga.kvack.org (Postfix) with ESMTP id D95008D0135 for ; Tue, 4 Aug 2020 05:15:18 -0400 (EDT) Received: from smtpin08.hostedemail.com (10.5.19.251.rfc1918.com [10.5.19.251]) by forelay03.hostedemail.com (Postfix) with ESMTP id 9550F8248047 for ; Tue, 4 Aug 2020 09:15:18 +0000 (UTC) X-FDA: 77112327516.08.berry10_2b1841226fa5 Received: from filter.hostedemail.com (10.5.16.251.rfc1918.com [10.5.16.251]) by smtpin08.hostedemail.com (Postfix) with ESMTP id 6BBEF1819E76C for ; Tue, 4 Aug 2020 09:15:18 +0000 (UTC) X-Spam-Summary: 1,0,0,,d41d8cd98f00b204,prvs=478224244=sjpark@amazon.com,,RULES_HIT:30003:30034:30051:30054:30064:30067:30070:30075:30080,0,RBL:207.171.184.29:@amazon.com:.lbl8.mailshell.net-62.18.0.100 66.10.201.10;04yrpqpqochcgdkcdrduut3oauu6dycwdgzkx7bioeaz9y5z757se6ixt36hid3.rhwhwp57ndbqsqddkd3qgiqgp48i95ugsu9kcsz6pd46rzq1eeyxme4uhebd9uk.g-lbl8.mailshell.net-223.238.255.100,CacheIP:none,Bayesian:0.5,0.5,0.5,Netcheck:none,DomainCache:0,MSF:not bulk,SPF:fp,MSBL:0,DNSBL:neutral,Custom_rules:0:0:0,LFtime:24,LUA_SUMMARY:none X-HE-Tag: berry10_2b1841226fa5 X-Filterd-Recvd-Size: 12163 Received: from smtp-fw-9102.amazon.com (smtp-fw-9102.amazon.com [207.171.184.29]) by imf01.hostedemail.com (Postfix) with ESMTP for ; Tue, 4 Aug 2020 09:15:17 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=amazon.com; i=@amazon.com; q=dns/txt; s=amazon201209; t=1596532517; x=1628068517; h=from:to:cc:subject:date:message-id:in-reply-to: references:mime-version; bh=9329NkJ5BUGBukxFxLfzY1st0KWTc8HMJ9MvZIrqFng=; b=BinWGlmRCad2/QdtPkhPvvcbtEYGwQcustqNWYLaySGCoq3EdsnW8U2d Q4jauD7a+Oz0KGCLkUmXNf6jO8hGWKHe2RjYMiCrAU4KJvpwEqWElgEnW zAhnPLbbMr0xzIp5tsdXpfICOQhJiXvmNWZMzyy3P+78P2eD6fShmVxVs w=; IronPort-SDR: 9wusgSY9ngetMrAY4x/qH+9fQJNTBtk7sFPBcdZraAovr1/TcfCayuy1iazfrH/sMdNPR1mtpZ dSdLZKNWIn7Q== X-IronPort-AV: E=Sophos;i="5.75,433,1589241600"; d="scan'208";a="65399680" Received: from sea32-co-svc-lb4-vlan3.sea.corp.amazon.com (HELO email-inbound-relay-2c-579b7f5b.us-west-2.amazon.com) ([10.47.23.38]) by smtp-border-fw-out-9102.sea19.amazon.com with ESMTP; 04 Aug 2020 09:15:14 +0000 Received: from EX13MTAUEA002.ant.amazon.com (pdx4-ws-svc-p6-lb7-vlan3.pdx.amazon.com [10.170.41.166]) by email-inbound-relay-2c-579b7f5b.us-west-2.amazon.com (Postfix) with ESMTPS id B68C7A2A1C; Tue, 4 Aug 2020 09:15:11 +0000 (UTC) Received: from EX13D31EUA001.ant.amazon.com (10.43.165.15) by EX13MTAUEA002.ant.amazon.com (10.43.61.77) with Microsoft SMTP Server (TLS) id 15.0.1497.2; Tue, 4 Aug 2020 09:15:11 +0000 Received: from u886c93fd17d25d.ant.amazon.com (10.43.162.248) by EX13D31EUA001.ant.amazon.com (10.43.165.15) with Microsoft SMTP Server (TLS) id 15.0.1497.2; Tue, 4 Aug 2020 09:14:51 +0000 From: SeongJae Park To: CC: SeongJae Park , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , Subject: [PATCH v19 01/15] mm: Introduce Data Access MONitor (DAMON) Date: Tue, 4 Aug 2020 11:14:02 +0200 Message-ID: <20200804091416.31039-2-sjpark@amazon.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20200804091416.31039-1-sjpark@amazon.com> References: <20200804091416.31039-1-sjpark@amazon.com> MIME-Version: 1.0 X-Originating-IP: [10.43.162.248] X-ClientProxiedBy: EX13D36UWA004.ant.amazon.com (10.43.160.175) To EX13D31EUA001.ant.amazon.com (10.43.165.15) X-Rspamd-Queue-Id: 6BBEF1819E76C X-Spamd-Result: default: False [0.00 / 100.00] X-Rspamd-Server: rspam01 X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: From: SeongJae Park DAMON is a data access monitoring framework subsystem for the Linux kernel. The core mechanisms of DAMON make it - accurate (the monitoring output is useful enough for DRAM level memory management; It might not appropriate for CPU Cache levels, though), - light-weight (the monitoring overhead is low enough to be applied online), and - scalable (the upper-bound of the overhead is in constant range regardless of the size of target workloads). Using this framework, therefore, the kernel's memory management mechanisms can make advanced decisions. Experimental memory management optimization works that incurring high data accesses monitoring overhead could implemented again. In user space, meanwhile, users who have some special workloads can write personalized applications for better understanding and optimizations of their workloads and systems. This commit is implementing only the stub for the initialization, basic data structures, and simple manipulation functions of the structures. The core mechanisms of DAMON will be implemented by following commits. Signed-off-by: SeongJae Park Reviewed-by: Leonard Foerster Reviewed-by: Varad Gautam Signed-off-by: SeongJae Park --- include/linux/damon.h | 66 ++++++++++++++++ mm/Kconfig | 11 +++ mm/Makefile | 1 + mm/damon.c | 176 ++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 254 insertions(+) create mode 100644 include/linux/damon.h create mode 100644 mm/damon.c diff --git a/include/linux/damon.h b/include/linux/damon.h new file mode 100644 index 000000000000..a6e839a236f4 --- /dev/null +++ b/include/linux/damon.h @@ -0,0 +1,66 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +/* + * DAMON api + * + * Copyright 2019-2020 Amazon.com, Inc. or its affiliates. + * + * Author: SeongJae Park + */ + +#ifndef _DAMON_H_ +#define _DAMON_H_ + +#include +#include + +/** + * struct damon_addr_range - Represents an address region of [@start, @end). + * @start: Start address of the region (inclusive). + * @end: End address of the region (exclusive). + */ +struct damon_addr_range { + unsigned long start; + unsigned long end; +}; + +/** + * struct damon_region - Represents a monitoring target region. + * @ar: The address range of the region. + * @sampling_addr: Address of the sample for the next access check. + * @nr_accesses: Access frequency of this region. + * @list: List head for siblings. + */ +struct damon_region { + struct damon_addr_range ar; + unsigned long sampling_addr; + unsigned int nr_accesses; + struct list_head list; +}; + +/** + * struct damon_target - Represents a monitoring target. + * @id: Unique identifier for this target. + * @regions_list: Head of the monitoring target regions of this target. + * @list: List head for siblings. + * + * Each monitoring context could have multiple targets. For example, a context + * for virtual memory address spaces could have multiple target processes. The + * @id of each target should be unique among the targets of the context. For + * example, in the virtual address monitoring context, it could be a pidfd or + * an address of an mm_struct. + */ +struct damon_target { + unsigned long id; + struct list_head regions_list; + struct list_head list; +}; + +/** + * struct damon_ctx - Represents a context for each monitoring. + * @targets_list: Head of monitoring targets (&damon_target) list. + */ +struct damon_ctx { + struct list_head targets_list; /* 'damon_target' objects */ +}; + +#endif diff --git a/mm/Kconfig b/mm/Kconfig index f2104cc0d35c..a99d755d67d3 100644 --- a/mm/Kconfig +++ b/mm/Kconfig @@ -872,4 +872,15 @@ config ARCH_HAS_HUGEPD config MAPPING_DIRTY_HELPERS bool +config DAMON + bool "Data Access Monitor" + help + This feature allows to monitor access frequency of each memory + region. The information can be useful for performance-centric DRAM + level memory management. + + See https://damonitor.github.io/doc/html/latest-damon/index.html for + more information. + If unsure, say N. + endmenu diff --git a/mm/Makefile b/mm/Makefile index 6e9d46b2efc9..30c5dba52fb2 100644 --- a/mm/Makefile +++ b/mm/Makefile @@ -121,3 +121,4 @@ obj-$(CONFIG_MEMFD_CREATE) += memfd.o obj-$(CONFIG_MAPPING_DIRTY_HELPERS) += mapping_dirty_helpers.o obj-$(CONFIG_PTDUMP_CORE) += ptdump.o obj-$(CONFIG_PAGE_REPORTING) += page_reporting.o +obj-$(CONFIG_DAMON) += damon.o diff --git a/mm/damon.c b/mm/damon.c new file mode 100644 index 000000000000..d446ba4bfb0a --- /dev/null +++ b/mm/damon.c @@ -0,0 +1,176 @@ +// SPDX-License-Identifier: GPL-2.0 +/* + * Data Access Monitor + * + * Copyright 2019-2020 Amazon.com, Inc. or its affiliates. + * + * Author: SeongJae Park + * + * This file is constructed in below parts. + * + * - Functions and macros for DAMON data structures + * - Functions for the initialization + * + * The core parts are not implemented yet. + */ + +#define pr_fmt(fmt) "damon: " fmt + +#include +#include +#include +#include + +/* + * Functions and macros for DAMON data structures + */ + +#define damon_next_region(r) \ + (container_of(r->list.next, struct damon_region, list)) + +#define damon_prev_region(r) \ + (container_of(r->list.prev, struct damon_region, list)) + +#define damon_for_each_region(r, t) \ + list_for_each_entry(r, &t->regions_list, list) + +#define damon_for_each_region_safe(r, next, t) \ + list_for_each_entry_safe(r, next, &t->regions_list, list) + +#define damon_for_each_target(t, ctx) \ + list_for_each_entry(t, &(ctx)->targets_list, list) + +#define damon_for_each_target_safe(t, next, ctx) \ + list_for_each_entry_safe(t, next, &(ctx)->targets_list, list) + +/* Get a random number in [l, r) */ +#define damon_rand(l, r) (l + prandom_u32() % (r - l)) + +/* + * Construct a damon_region struct + * + * Returns the pointer to the new struct if success, or NULL otherwise + */ +static struct damon_region *damon_new_region(unsigned long start, + unsigned long end) +{ + struct damon_region *region; + + region = kmalloc(sizeof(*region), GFP_KERNEL); + if (!region) + return NULL; + + region->ar.start = start; + region->ar.end = end; + region->nr_accesses = 0; + INIT_LIST_HEAD(®ion->list); + + return region; +} + +/* + * Add a region between two other regions + */ +static inline void damon_insert_region(struct damon_region *r, + struct damon_region *prev, struct damon_region *next) +{ + __list_add(&r->list, &prev->list, &next->list); +} + +static void damon_add_region(struct damon_region *r, struct damon_target *t) +{ + list_add_tail(&r->list, &t->regions_list); +} + +static void damon_del_region(struct damon_region *r) +{ + list_del(&r->list); +} + +static void damon_free_region(struct damon_region *r) +{ + kfree(r); +} + +static void damon_destroy_region(struct damon_region *r) +{ + damon_del_region(r); + damon_free_region(r); +} + +/* + * Construct a damon_target struct + * + * Returns the pointer to the new struct if success, or NULL otherwise + */ +static struct damon_target *damon_new_target(unsigned long id) +{ + struct damon_target *t; + + t = kmalloc(sizeof(*t), GFP_KERNEL); + if (!t) + return NULL; + + t->id = id; + INIT_LIST_HEAD(&t->regions_list); + + return t; +} + +static void damon_add_target(struct damon_ctx *ctx, struct damon_target *t) +{ + list_add_tail(&t->list, &ctx->targets_list); +} + +static void damon_del_target(struct damon_target *t) +{ + list_del(&t->list); +} + +static void damon_free_target(struct damon_target *t) +{ + struct damon_region *r, *next; + + damon_for_each_region_safe(r, next, t) + damon_free_region(r); + kfree(t); +} + +static void damon_destroy_target(struct damon_target *t) +{ + damon_del_target(t); + damon_free_target(t); +} + +static unsigned int nr_damon_targets(struct damon_ctx *ctx) +{ + struct damon_target *t; + unsigned int nr_targets = 0; + + damon_for_each_target(t, ctx) + nr_targets++; + + return nr_targets; +} + +static unsigned int nr_damon_regions(struct damon_target *t) +{ + struct damon_region *r; + unsigned int nr_regions = 0; + + damon_for_each_region(r, t) + nr_regions++; + + return nr_regions; +} + +/* + * Functions for the initialization + */ + +static int __init damon_init(void) +{ + return 0; +} + +module_init(damon_init);