From patchwork Mon Aug 17 10:51:23 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: SeongJae Park X-Patchwork-Id: 11717983 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 883C0109B for ; Mon, 17 Aug 2020 10:52:51 +0000 (UTC) Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by mail.kernel.org (Postfix) with ESMTP id 447B1207DE for ; Mon, 17 Aug 2020 10:52:51 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (1024-bit key) header.d=amazon.com header.i=@amazon.com header.b="YLMLYiCQ" DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org 447B1207DE 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 8191E6B0007; Mon, 17 Aug 2020 06:52:50 -0400 (EDT) Delivered-To: linux-mm-outgoing@kvack.org Received: by kanga.kvack.org (Postfix, from userid 40) id 7A2166B0008; Mon, 17 Aug 2020 06:52:50 -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 6426A6B000A; Mon, 17 Aug 2020 06:52:50 -0400 (EDT) X-Original-To: linux-mm@kvack.org X-Delivered-To: linux-mm@kvack.org Received: from forelay.hostedemail.com (smtprelay0075.hostedemail.com [216.40.44.75]) by kanga.kvack.org (Postfix) with ESMTP id 4D1526B0007 for ; Mon, 17 Aug 2020 06:52:50 -0400 (EDT) Received: from smtpin26.hostedemail.com (10.5.19.251.rfc1918.com [10.5.19.251]) by forelay02.hostedemail.com (Postfix) with ESMTP id 0C3BC363F for ; Mon, 17 Aug 2020 10:52:50 +0000 (UTC) X-FDA: 77159747700.26.tree14_6301a9a27016 Received: from filter.hostedemail.com (10.5.16.251.rfc1918.com [10.5.16.251]) by smtpin26.hostedemail.com (Postfix) with ESMTP id C660F1804B661 for ; Mon, 17 Aug 2020 10:52:49 +0000 (UTC) X-Spam-Summary: 1,0,0,,d41d8cd98f00b204,prvs=491cff689=sjpark@amazon.com,,RULES_HIT:30003:30034:30051:30054:30064:30067:30070:30075:30080,0,RBL:207.171.190.10:@amazon.com:.lbl8.mailshell.net-66.10.201.10 62.18.0.100;04ygy54mazjzmd65ddmrbqndkoi56ocwdgzkx7bioeaz9y5z757se6ixt36hid3.rhwhwp5pjeid99qzkd3qgiqgp48i95ugsu9kcsz6pd46rzq1eeyxme4uhebd9uk.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:23,LUA_SUMMARY:none X-HE-Tag: tree14_6301a9a27016 X-Filterd-Recvd-Size: 12041 Received: from smtp-fw-33001.amazon.com (smtp-fw-33001.amazon.com [207.171.190.10]) by imf17.hostedemail.com (Postfix) with ESMTP for ; Mon, 17 Aug 2020 10:52:48 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=amazon.com; i=@amazon.com; q=dns/txt; s=amazon201209; t=1597661569; x=1629197569; h=from:to:cc:subject:date:message-id:in-reply-to: references:mime-version; bh=EyPE9Guy6K8Ykgz/GFVPQxJeVx8vx3JyIj/anqhEN08=; b=YLMLYiCQBQq1P+07mxLcKwPZV9p8eJgXKVe26CuJ0CYH6ex/RS0S56E2 +kgHvM1wY1QoM4rIpeORRx2x+tkAmlEyx0sxtvzKYd1rlvYpopFqUa3ty UmHWl2vNE5eeI5+MmrqFP2sTcageqVVdZdFUG0i8zxv05bGSOZclY9S0h g=; X-IronPort-AV: E=Sophos;i="5.76,322,1592870400"; d="scan'208";a="67283530" Received: from sea32-co-svc-lb4-vlan3.sea.corp.amazon.com (HELO email-inbound-relay-2a-f14f4a47.us-west-2.amazon.com) ([10.47.23.38]) by smtp-border-fw-out-33001.sea14.amazon.com with ESMTP; 17 Aug 2020 10:52:40 +0000 Received: from EX13MTAUEA001.ant.amazon.com (pdx4-ws-svc-p6-lb7-vlan2.pdx.amazon.com [10.170.41.162]) by email-inbound-relay-2a-f14f4a47.us-west-2.amazon.com (Postfix) with ESMTPS id 0357DA18DF; Mon, 17 Aug 2020 10:52:37 +0000 (UTC) Received: from EX13D31EUA001.ant.amazon.com (10.43.165.15) by EX13MTAUEA001.ant.amazon.com (10.43.61.82) with Microsoft SMTP Server (TLS) id 15.0.1497.2; Mon, 17 Aug 2020 10:52:37 +0000 Received: from u3f2cd687b01c55.ant.amazon.com (10.43.160.192) by EX13D31EUA001.ant.amazon.com (10.43.165.15) with Microsoft SMTP Server (TLS) id 15.0.1497.2; Mon, 17 Aug 2020 10:52:20 +0000 From: SeongJae Park To: CC: SeongJae Park , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , Subject: [PATCH v20 01/15] mm: Introduce Data Access MONitor (DAMON) Date: Mon, 17 Aug 2020 12:51:23 +0200 Message-ID: <20200817105137.19296-2-sjpark@amazon.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20200817105137.19296-1-sjpark@amazon.com> References: <20200817105137.19296-1-sjpark@amazon.com> MIME-Version: 1.0 X-Originating-IP: [10.43.160.192] X-ClientProxiedBy: EX13D02UWC004.ant.amazon.com (10.43.162.236) To EX13D31EUA001.ant.amazon.com (10.43.165.15) X-Rspamd-Queue-Id: C660F1804B661 X-Spamd-Result: default: False [0.00 / 100.00] X-Rspamd-Server: rspam02 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 --- 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); From patchwork Mon Aug 17 10:51:24 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: SeongJae Park X-Patchwork-Id: 11717987 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 EDD8713A4 for ; Mon, 17 Aug 2020 10:53:12 +0000 (UTC) Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by mail.kernel.org (Postfix) with ESMTP id 9DBA3207DE for ; Mon, 17 Aug 2020 10:53:12 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (1024-bit key) header.d=amazon.com header.i=@amazon.com header.b="vfLaOcuV" DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org 9DBA3207DE 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 CFAD46B0008; Mon, 17 Aug 2020 06:53:11 -0400 (EDT) Delivered-To: linux-mm-outgoing@kvack.org Received: by kanga.kvack.org (Postfix, from userid 40) id CA9EA6B000A; Mon, 17 Aug 2020 06:53:11 -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 B73776B000C; Mon, 17 Aug 2020 06:53:11 -0400 (EDT) X-Original-To: linux-mm@kvack.org X-Delivered-To: linux-mm@kvack.org Received: from forelay.hostedemail.com (smtprelay0027.hostedemail.com [216.40.44.27]) by kanga.kvack.org (Postfix) with ESMTP id 984066B0008 for ; Mon, 17 Aug 2020 06:53:11 -0400 (EDT) Received: from smtpin30.hostedemail.com (10.5.19.251.rfc1918.com [10.5.19.251]) by forelay01.hostedemail.com (Postfix) with ESMTP id 4FD26180AD817 for ; Mon, 17 Aug 2020 10:53:11 +0000 (UTC) X-FDA: 77159748582.30.eyes23_071512c27016 Received: from filter.hostedemail.com (10.5.16.251.rfc1918.com [10.5.16.251]) by smtpin30.hostedemail.com (Postfix) with ESMTP id 18826180B3C83 for ; Mon, 17 Aug 2020 10:53:11 +0000 (UTC) X-Spam-Summary: 1,0,0,,d41d8cd98f00b204,prvs=491cff689=sjpark@amazon.com,,RULES_HIT:30003:30012:30034:30051:30054:30056:30064:30070:30075,0,RBL:52.95.49.90:@amazon.com:.lbl8.mailshell.net-62.18.0.100 64.10.201.10;04yg5o5wyrp8nb1tr3sy7cu1afj9foc4rn5uduf715qq6bunnt6gi34rm7wj9mo.syjbxx1gnhrwa5q1yh9c5qg7h5y9tkp1q5sane96upsqy1eewphhtnzjyjqdpsi.h-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:26,LUA_SUMMARY:none X-HE-Tag: eyes23_071512c27016 X-Filterd-Recvd-Size: 20313 Received: from smtp-fw-6002.amazon.com (smtp-fw-6002.amazon.com [52.95.49.90]) by imf07.hostedemail.com (Postfix) with ESMTP for ; Mon, 17 Aug 2020 10:53:10 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=amazon.com; i=@amazon.com; q=dns/txt; s=amazon201209; t=1597661591; x=1629197591; h=from:to:cc:subject:date:message-id:in-reply-to: references:mime-version; bh=TNF6XKUrmUMCS4tn1gAUd0+yYzG+eTDASEOR2XFrOvI=; b=vfLaOcuVBdqM7/pVQ9JWZg0QB0Aw+0I3RUSL8Sw/5Zl0yJSfvAhBVS77 eyOX7XWj/c6NoegbX2GeEkAsJWn+u9+TfwG4x5r9ZFYx+5GtPKLbQh9jI oa2OlfFnNGwgfDzRWt7kZQwfiNMtAu3pYO7fy5PQAVEMldKLEwadeLg6Z A=; X-IronPort-AV: E=Sophos;i="5.76,322,1592870400"; d="scan'208";a="48181911" Received: from iad12-co-svc-p1-lb1-vlan3.amazon.com (HELO email-inbound-relay-1a-e34f1ddc.us-east-1.amazon.com) ([10.43.8.6]) by smtp-border-fw-out-6002.iad6.amazon.com with ESMTP; 17 Aug 2020 10:53:10 +0000 Received: from EX13MTAUEA002.ant.amazon.com (iad55-ws-svc-p15-lb9-vlan3.iad.amazon.com [10.40.159.166]) by email-inbound-relay-1a-e34f1ddc.us-east-1.amazon.com (Postfix) with ESMTPS id CDCA8A213C; Mon, 17 Aug 2020 10:52:58 +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; Mon, 17 Aug 2020 10:52:57 +0000 Received: from u3f2cd687b01c55.ant.amazon.com (10.43.160.192) by EX13D31EUA001.ant.amazon.com (10.43.165.15) with Microsoft SMTP Server (TLS) id 15.0.1497.2; Mon, 17 Aug 2020 10:52:40 +0000 From: SeongJae Park To: CC: SeongJae Park , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , Subject: [PATCH v20 02/15] mm/damon: Implement region based sampling Date: Mon, 17 Aug 2020 12:51:24 +0200 Message-ID: <20200817105137.19296-3-sjpark@amazon.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20200817105137.19296-1-sjpark@amazon.com> References: <20200817105137.19296-1-sjpark@amazon.com> MIME-Version: 1.0 X-Originating-IP: [10.43.160.192] X-ClientProxiedBy: EX13D02UWC004.ant.amazon.com (10.43.162.236) To EX13D31EUA001.ant.amazon.com (10.43.165.15) X-Rspamd-Queue-Id: 18826180B3C83 X-Spamd-Result: default: False [0.00 / 100.00] X-Rspamd-Server: rspam05 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 separates its monitoring target address space independent high level logics from the target space dependent low level primitives for flexible support of various address spaces. This commit implements DAMON's target address space independent high level logics for basic access check and region based sampling. Hence, without the target address space specific parts implementations, this doesn't work alone. A reference implementation of those will be provided by a later commit. Basic Access Check ================== The output of DAMON says what pages are how frequently accessed for a given duration. The resolution of the access frequency is controlled by setting ``sampling interval`` and ``aggregation interval``. In detail, DAMON checks access to each page per ``sampling interval`` and aggregates the results. In other words, counts the number of the accesses to each page. After each ``aggregation interval`` passes, DAMON calls callback functions that previously registered by users so that users can read the aggregated results and then clears the results. This can be described in below simple pseudo-code:: while monitoring_on: for page in monitoring_target: if accessed(page): nr_accesses[page] += 1 if time() % aggregation_interval == 0: for callback in user_registered_callbacks: callback(monitoring_target, nr_accesses) for page in monitoring_target: nr_accesses[page] = 0 sleep(sampling interval) The monitoring overhead of this mechanism will arbitrarily increase as the size of the target workload grows. Region Based Sampling ===================== To avoid the unbounded increase of the overhead, DAMON groups adjacent pages that assumed to have the same access frequencies into a region. As long as the assumption (pages in a region have the same access frequencies) is kept, only one page in the region is required to be checked. Thus, for each ``sampling interval``, DAMON randomly picks one page in each region, waits for one ``sampling interval``, checks whether the page is accessed meanwhile, and increases the access frequency of the region if so. Therefore, the monitoring overhead is controllable by setting the number of regions. DAMON allows users to set the minimum and the maximum number of regions for the trade-off. This scheme, however, cannot preserve the quality of the output if the assumption is not guaranteed. Next commit will address this problem. Signed-off-by: SeongJae Park Reviewed-by: Leonard Foerster --- include/linux/damon.h | 93 +++++++++++- mm/damon.c | 323 +++++++++++++++++++++++++++++++++++++++++- 2 files changed, 413 insertions(+), 3 deletions(-) diff --git a/include/linux/damon.h b/include/linux/damon.h index a6e839a236f4..e0c8ea8f4091 100644 --- a/include/linux/damon.h +++ b/include/linux/damon.h @@ -11,6 +11,8 @@ #define _DAMON_H_ #include +#include +#include #include /** @@ -56,11 +58,100 @@ struct damon_target { }; /** - * struct damon_ctx - Represents a context for each monitoring. + * struct damon_ctx - Represents a context for each monitoring. This is the + * main interface that allows users to set the attributes and get the results + * of the monitoring. + * + * @sample_interval: The time between access samplings. + * @aggr_interval: The time between monitor results aggregations. + * @nr_regions: The number of monitoring regions. + * + * For each @sample_interval, DAMON checks whether each region is accessed or + * not. It aggregates and keeps the access information (number of accesses to + * each region) for @aggr_interval time. All time intervals are in + * micro-seconds. + * + * @kdamond: Kernel thread who does the monitoring. + * @kdamond_stop: Notifies whether kdamond should stop. + * @kdamond_lock: Mutex for the synchronizations with @kdamond. + * + * For each monitoring context, one kernel thread for the monitoring is + * created. The pointer to the thread is stored in @kdamond. + * + * Once started, the monitoring thread runs until explicitly required to be + * terminated or every monitoring target is invalid. The validity of the + * targets is checked via the @target_valid callback. The termination can also + * be explicitly requested by writing non-zero to @kdamond_stop. The thread + * sets @kdamond to NULL when it terminates. Therefore, users can know whether + * the monitoring is ongoing or terminated by reading @kdamond. Reads and + * writes to @kdamond and @kdamond_stop from outside of the monitoring thread + * must be protected by @kdamond_lock. + * + * Note that the monitoring thread protects only @kdamond and @kdamond_stop via + * @kdamond_lock. Accesses to other fields must be protected by themselves. + * * @targets_list: Head of monitoring targets (&damon_target) list. + * + * @init_target_regions: Constructs initial monitoring target regions. + * @prepare_access_checks: Prepares next access check of target regions. + * @check_accesses: Checks the access of target regions. + * @target_valid: Determine if the target is valid. + * @cleanup: Cleans up the context. + * @sample_cb: Called for each sampling interval. + * @aggregate_cb: Called for each aggregation interval. + * + * DAMON can be extended for various address spaces by users. For this, users + * can register the target address space dependent low level functions for + * their usecases via the callback pointers of the context. The monitoring + * thread calls @init_target_regions before starting the monitoring, and + * @prepare_access_checks, @check_accesses, and @target_valid for each + * @sample_interval. + * + * @init_target_regions should construct proper monitoring target regions and + * link those to the DAMON context struct. + * @prepare_access_checks should manipulate the monitoring regions to be + * prepare for the next access check. + * @check_accesses should check the accesses to each region that made after the + * last preparation and update the `->nr_accesses` of each region. + * @target_valid should check whether the target is still valid for the + * monitoring. + * @cleanup is called from @kdamond just before its termination. After this + * call, only @kdamond_lock and @kdamond will be touched. + * + * @sample_cb and @aggregate_cb are called from @kdamond for each of the + * sampling intervals and aggregation intervals, respectively. Therefore, + * users can safely access to the monitoring results via @targets_list without + * additional protection of @kdamond_lock. For the reason, users are + * recommended to use these callback for the accesses to the results. */ struct damon_ctx { + unsigned long sample_interval; + unsigned long aggr_interval; + unsigned long nr_regions; + + struct timespec64 last_aggregation; + + struct task_struct *kdamond; + bool kdamond_stop; + struct mutex kdamond_lock; + struct list_head targets_list; /* 'damon_target' objects */ + + /* callbacks */ + void (*init_target_regions)(struct damon_ctx *context); + void (*prepare_access_checks)(struct damon_ctx *context); + unsigned int (*check_accesses)(struct damon_ctx *context); + bool (*target_valid)(struct damon_target *target); + void (*cleanup)(struct damon_ctx *context); + void (*sample_cb)(struct damon_ctx *context); + void (*aggregate_cb)(struct damon_ctx *context); }; +int damon_set_targets(struct damon_ctx *ctx, + unsigned long *ids, ssize_t nr_ids); +int damon_set_attrs(struct damon_ctx *ctx, unsigned long sample_int, + unsigned long aggr_int, unsigned long min_nr_reg); +int damon_start(struct damon_ctx *ctxs, int nr_ctxs); +int damon_stop(struct damon_ctx *ctxs, int nr_ctxs); + #endif diff --git a/mm/damon.c b/mm/damon.c index d446ba4bfb0a..408f3a66a8d9 100644 --- a/mm/damon.c +++ b/mm/damon.c @@ -9,18 +9,27 @@ * This file is constructed in below parts. * * - Functions and macros for DAMON data structures + * - Functions for DAMON core logics and features + * - Functions for the DAMON programming interface * - Functions for the initialization - * - * The core parts are not implemented yet. */ #define pr_fmt(fmt) "damon: " fmt #include +#include +#include #include #include +#include +#include +#include +#include #include +/* Minimal region size. Every damon_region is aligned by this. */ +#define MIN_REGION PAGE_SIZE + /* * Functions and macros for DAMON data structures */ @@ -46,6 +55,9 @@ /* Get a random number in [l, r) */ #define damon_rand(l, r) (l + prandom_u32() % (r - l)) +static DEFINE_MUTEX(damon_lock); +static int nr_running_ctxs; + /* * Construct a damon_region struct * @@ -164,6 +176,313 @@ static unsigned int nr_damon_regions(struct damon_target *t) return nr_regions; } +/* + * Functions for DAMON core logics and features + */ + +/* + * damon_check_reset_time_interval() - Check if a time interval is elapsed. + * @baseline: the time to check whether the interval has elapsed since + * @interval: the time interval (microseconds) + * + * See whether the given time interval has passed since the given baseline + * time. If so, it also updates the baseline to current time for next check. + * + * Return: true if the time interval has passed, or false otherwise. + */ +static bool damon_check_reset_time_interval(struct timespec64 *baseline, + unsigned long interval) +{ + struct timespec64 now; + + ktime_get_coarse_ts64(&now); + if ((timespec64_to_ns(&now) - timespec64_to_ns(baseline)) < + interval * 1000) + return false; + *baseline = now; + return true; +} + +/* + * Check whether it is time to flush the aggregated information + */ +static bool kdamond_aggregate_interval_passed(struct damon_ctx *ctx) +{ + return damon_check_reset_time_interval(&ctx->last_aggregation, + ctx->aggr_interval); +} + +/* + * Reset the aggregated monitoring results + */ +static void kdamond_reset_aggregated(struct damon_ctx *c) +{ + struct damon_target *t; + struct damon_region *r; + + damon_for_each_target(t, c) { + damon_for_each_region(r, t) + r->nr_accesses = 0; + } +} + +/* + * Check whether current monitoring should be stopped + * + * The monitoring is stopped when either the user requested to stop, or all + * monitoring targets are invalid. + * + * Returns true if need to stop current monitoring. + */ +static bool kdamond_need_stop(struct damon_ctx *ctx) +{ + struct damon_target *t; + bool stop; + + mutex_lock(&ctx->kdamond_lock); + stop = ctx->kdamond_stop; + mutex_unlock(&ctx->kdamond_lock); + if (stop) + return true; + + if (!ctx->target_valid) + return false; + + damon_for_each_target(t, ctx) { + if (ctx->target_valid(t)) + return false; + } + + return true; +} + +/* + * The monitoring daemon that runs as a kernel thread + */ +static int kdamond_fn(void *data) +{ + struct damon_ctx *ctx = (struct damon_ctx *)data; + struct damon_target *t; + struct damon_region *r, *next; + + pr_info("kdamond (%d) starts\n", ctx->kdamond->pid); + if (ctx->init_target_regions) + ctx->init_target_regions(ctx); + while (!kdamond_need_stop(ctx)) { + if (ctx->prepare_access_checks) + ctx->prepare_access_checks(ctx); + if (ctx->sample_cb) + ctx->sample_cb(ctx); + + usleep_range(ctx->sample_interval, ctx->sample_interval + 1); + + if (ctx->check_accesses) + ctx->check_accesses(ctx); + + if (kdamond_aggregate_interval_passed(ctx)) { + if (ctx->aggregate_cb) + ctx->aggregate_cb(ctx); + kdamond_reset_aggregated(ctx); + } + + } + damon_for_each_target(t, ctx) { + damon_for_each_region_safe(r, next, t) + damon_destroy_region(r); + } + + if (ctx->cleanup) + ctx->cleanup(ctx); + + pr_debug("kdamond (%d) finishes\n", ctx->kdamond->pid); + mutex_lock(&ctx->kdamond_lock); + ctx->kdamond = NULL; + mutex_unlock(&ctx->kdamond_lock); + + mutex_lock(&damon_lock); + nr_running_ctxs--; + mutex_unlock(&damon_lock); + + do_exit(0); +} + +/* + * Functions for the DAMON programming interface + */ + +static bool damon_kdamond_running(struct damon_ctx *ctx) +{ + bool running; + + mutex_lock(&ctx->kdamond_lock); + running = ctx->kdamond != NULL; + mutex_unlock(&ctx->kdamond_lock); + + return running; +} + +/* + * __damon_start() - Starts monitoring with given context. + * @ctx: monitoring context + * + * Return: 0 on success, negative error code otherwise. + */ +static int __damon_start(struct damon_ctx *ctx) +{ + int err = -EBUSY; + + mutex_lock(&ctx->kdamond_lock); + if (!ctx->kdamond) { + err = 0; + ctx->kdamond_stop = false; + ctx->kdamond = kthread_create(kdamond_fn, ctx, "kdamond"); + if (IS_ERR(ctx->kdamond)) + err = PTR_ERR(ctx->kdamond); + else + wake_up_process(ctx->kdamond); + } + mutex_unlock(&ctx->kdamond_lock); + + return err; +} + +/** + * damon_start() - Starts the monitorings for a given group of contexts. + * @ctxs: an array of the contexts to start monitoring + * @nr_ctxs: size of @ctxs + * + * This function starts a group of monitoring threads for a group of monitoring + * contexts. One thread per each context is created and run concurrently. The + * caller should handle synchronization between the threads by itself. If a + * group of threads that created by other 'damon_start()' call is currently + * running, this function does nothing but returns -EBUSY. + * + * Return: 0 on success, negative error code otherwise. + */ +int damon_start(struct damon_ctx *ctxs, int nr_ctxs) +{ + int i; + int err = 0; + + mutex_lock(&damon_lock); + if (nr_running_ctxs) { + mutex_unlock(&damon_lock); + return -EBUSY; + } + + for (i = 0; i < nr_ctxs; i++) { + err = __damon_start(&ctxs[i]); + if (err) + break; + nr_running_ctxs++; + } + mutex_unlock(&damon_lock); + + return err; +} + +/* + * __damon_stop() - Stops monitoring of given context. + * @ctx: monitoring context + * + * Return: 0 on success, negative error code otherwise. + */ +static int __damon_stop(struct damon_ctx *ctx) +{ + mutex_lock(&ctx->kdamond_lock); + if (ctx->kdamond) { + ctx->kdamond_stop = true; + mutex_unlock(&ctx->kdamond_lock); + while (damon_kdamond_running(ctx)) + usleep_range(ctx->sample_interval, + ctx->sample_interval * 2); + return 0; + } + mutex_unlock(&ctx->kdamond_lock); + + return -EPERM; +} + +/** + * damon_stop() - Stops the monitorings for a given group of contexts. + * @ctxs: an array of the contexts to stop monitoring + * @nr_ctxs: size of @ctxs + * + * Return: 0 on success, negative error code otherwise. + */ +int damon_stop(struct damon_ctx *ctxs, int nr_ctxs) +{ + int i, err = 0; + + for (i = 0; i < nr_ctxs; i++) { + /* nr_running_ctxs is decremented in kdamond_fn */ + err = __damon_stop(&ctxs[i]); + if (err) + return err; + } + + return err; +} + +/** + * damon_set_targets() - Set monitoring targets. + * @ctx: monitoring context + * @ids: array of target ids + * @nr_ids: number of entries in @ids + * + * This function should not be called while the kdamond is running. + * + * Return: 0 on success, negative error code otherwise. + */ +int damon_set_targets(struct damon_ctx *ctx, + unsigned long *ids, ssize_t nr_ids) +{ + ssize_t i; + struct damon_target *t, *next; + + damon_for_each_target_safe(t, next, ctx) + damon_destroy_target(t); + + for (i = 0; i < nr_ids; i++) { + t = damon_new_target(ids[i]); + if (!t) { + pr_err("Failed to alloc damon_target\n"); + return -ENOMEM; + } + damon_add_target(ctx, t); + } + + return 0; +} + +/** + * damon_set_attrs() - Set attributes for the monitoring. + * @ctx: monitoring context + * @sample_int: time interval between samplings + * @aggr_int: time interval between aggregations + * @nr_reg: number of regions + * + * This function should not be called while the kdamond is running. + * Every time interval is in micro-seconds. + * + * Return: 0 on success, negative error code otherwise. + */ +int damon_set_attrs(struct damon_ctx *ctx, unsigned long sample_int, + unsigned long aggr_int, unsigned long nr_reg) +{ + if (nr_reg < 3) { + pr_err("nr_regions (%lu) must be at least 3\n", + nr_reg); + return -EINVAL; + } + + ctx->sample_interval = sample_int; + ctx->aggr_interval = aggr_int; + ctx->nr_regions = nr_reg; + + return 0; +} + /* * Functions for the initialization */ From patchwork Mon Aug 17 10:51:25 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: SeongJae Park X-Patchwork-Id: 11717989 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 68B88109B for ; Mon, 17 Aug 2020 10:53:49 +0000 (UTC) Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by mail.kernel.org (Postfix) with ESMTP id 272FD20758 for ; Mon, 17 Aug 2020 10:53:49 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (1024-bit key) header.d=amazon.com header.i=@amazon.com header.b="X+PgZ+UK" DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org 272FD20758 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 5F5E76B0006; Mon, 17 Aug 2020 06:53:48 -0400 (EDT) Delivered-To: linux-mm-outgoing@kvack.org Received: by kanga.kvack.org (Postfix, from userid 40) id 57E0B6B000A; Mon, 17 Aug 2020 06:53:48 -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 41F108D0002; Mon, 17 Aug 2020 06:53:48 -0400 (EDT) X-Original-To: linux-mm@kvack.org X-Delivered-To: linux-mm@kvack.org Received: from forelay.hostedemail.com (smtprelay0117.hostedemail.com [216.40.44.117]) by kanga.kvack.org (Postfix) with ESMTP id 24D6B6B0006 for ; Mon, 17 Aug 2020 06:53:48 -0400 (EDT) Received: from smtpin01.hostedemail.com (10.5.19.251.rfc1918.com [10.5.19.251]) by forelay05.hostedemail.com (Postfix) with ESMTP id DA1CC181AEF3C for ; Mon, 17 Aug 2020 10:53:47 +0000 (UTC) X-FDA: 77159750094.01.snow18_2c11c0427016 Received: from filter.hostedemail.com (10.5.16.251.rfc1918.com [10.5.16.251]) by smtpin01.hostedemail.com (Postfix) with ESMTP id 9FA931004C797 for ; Mon, 17 Aug 2020 10:53:47 +0000 (UTC) X-Spam-Summary: 1,0,0,,d41d8cd98f00b204,prvs=491cff689=sjpark@amazon.com,,RULES_HIT:30012:30034:30054:30056:30064:30070:30075,0,RBL:207.171.190.10:@amazon.com:.lbl8.mailshell.net-62.18.0.100 66.10.201.10;04y857fsuswh7wtnj3ej7m7qimtzxycqqjnd3p17z758s8xx7uqe94hgq8itifp.xr8c6t5u3ama9ck3i4qh1joda678yizx5otrtj54shmc79ey1s1oi34dxxg6c6r.6-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: snow18_2c11c0427016 X-Filterd-Recvd-Size: 13637 Received: from smtp-fw-33001.amazon.com (smtp-fw-33001.amazon.com [207.171.190.10]) by imf29.hostedemail.com (Postfix) with ESMTP for ; Mon, 17 Aug 2020 10:53:46 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=amazon.com; i=@amazon.com; q=dns/txt; s=amazon201209; t=1597661627; x=1629197627; h=from:to:cc:subject:date:message-id:in-reply-to: references:mime-version; bh=LxXakDHxXGWfibQrSFhlgpGMJF4KLPu/ut4TN5+sISg=; b=X+PgZ+UKjb4R+xIYCsJUWUfx/9D2IyGK4m4qXUNvEZyHWPavLEthYVcd GLFr/AGU820DiIiAqR/S0TZkU/1Cum0dFuZiAdVoY4+ZBrxucpkqnF45d a7IALCnXOX7KoKts63QRJ9h99Z2CAma8F5fUiNrkyg8dEsvUlgbgoYpo1 U=; X-IronPort-AV: E=Sophos;i="5.76,322,1592870400"; d="scan'208";a="67283762" Received: from sea32-co-svc-lb4-vlan3.sea.corp.amazon.com (HELO email-inbound-relay-1a-7d76a15f.us-east-1.amazon.com) ([10.47.23.38]) by smtp-border-fw-out-33001.sea14.amazon.com with ESMTP; 17 Aug 2020 10:53:43 +0000 Received: from EX13MTAUEA002.ant.amazon.com (iad55-ws-svc-p15-lb9-vlan3.iad.amazon.com [10.40.159.166]) by email-inbound-relay-1a-7d76a15f.us-east-1.amazon.com (Postfix) with ESMTPS id 8BB1DA25BB; Mon, 17 Aug 2020 10:53:31 +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; Mon, 17 Aug 2020 10:53:30 +0000 Received: from u3f2cd687b01c55.ant.amazon.com (10.43.160.192) by EX13D31EUA001.ant.amazon.com (10.43.165.15) with Microsoft SMTP Server (TLS) id 15.0.1497.2; Mon, 17 Aug 2020 10:53:13 +0000 From: SeongJae Park To: CC: SeongJae Park , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , Subject: [PATCH v20 03/15] mm/damon: Adaptively adjust regions Date: Mon, 17 Aug 2020 12:51:25 +0200 Message-ID: <20200817105137.19296-4-sjpark@amazon.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20200817105137.19296-1-sjpark@amazon.com> References: <20200817105137.19296-1-sjpark@amazon.com> MIME-Version: 1.0 X-Originating-IP: [10.43.160.192] X-ClientProxiedBy: EX13D02UWC004.ant.amazon.com (10.43.162.236) To EX13D31EUA001.ant.amazon.com (10.43.165.15) X-Rspamd-Queue-Id: 9FA931004C797 X-Spamd-Result: default: False [0.00 / 100.00] X-Rspamd-Server: rspam02 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 Even somehow the initial monitoring target regions are well constructed to fulfill the assumption (pages in same region have similar access frequencies), the data access pattern can be dynamically changed. This will result in low monitoring quality. To keep the assumption as much as possible, DAMON adaptively merges and splits each region based on their access frequency. For each ``aggregation interval``, it compares the access frequencies of adjacent regions and merges those if the frequency difference is small. Then, after it reports and clears the aggregated access frequency of each region, it splits each region into two or three regions if the total number of regions will not exceed the user-specified maximum number of regions after the split. In this way, DAMON provides its best-effort quality and minimal overhead while keeping the upper-bound overhead that users set. Signed-off-by: SeongJae Park Reviewed-by: Leonard Foerster --- include/linux/damon.h | 11 ++- mm/damon.c | 191 ++++++++++++++++++++++++++++++++++++++++-- 2 files changed, 189 insertions(+), 13 deletions(-) diff --git a/include/linux/damon.h b/include/linux/damon.h index e0c8ea8f4091..708775a36be3 100644 --- a/include/linux/damon.h +++ b/include/linux/damon.h @@ -64,7 +64,8 @@ struct damon_target { * * @sample_interval: The time between access samplings. * @aggr_interval: The time between monitor results aggregations. - * @nr_regions: The number of monitoring regions. + * @min_nr_regions: The minimum number of monitoring regions. + * @max_nr_regions: The maximum number of monitoring regions. * * For each @sample_interval, DAMON checks whether each region is accessed or * not. It aggregates and keeps the access information (number of accesses to @@ -127,7 +128,8 @@ struct damon_target { struct damon_ctx { unsigned long sample_interval; unsigned long aggr_interval; - unsigned long nr_regions; + unsigned long min_nr_regions; + unsigned long max_nr_regions; struct timespec64 last_aggregation; @@ -149,8 +151,9 @@ struct damon_ctx { int damon_set_targets(struct damon_ctx *ctx, unsigned long *ids, ssize_t nr_ids); -int damon_set_attrs(struct damon_ctx *ctx, unsigned long sample_int, - unsigned long aggr_int, unsigned long min_nr_reg); +int damon_set_attrs(struct damon_ctx *ctx, + unsigned long sample_int, unsigned long aggr_int, + unsigned long min_nr_reg, unsigned long max_nr_reg); int damon_start(struct damon_ctx *ctxs, int nr_ctxs); int damon_stop(struct damon_ctx *ctxs, int nr_ctxs); diff --git a/mm/damon.c b/mm/damon.c index 408f3a66a8d9..13b17074d411 100644 --- a/mm/damon.c +++ b/mm/damon.c @@ -176,6 +176,26 @@ static unsigned int nr_damon_regions(struct damon_target *t) return nr_regions; } +/* Returns the size upper limit for each monitoring region */ +static unsigned long damon_region_sz_limit(struct damon_ctx *ctx) +{ + struct damon_target *t; + struct damon_region *r; + unsigned long sz = 0; + + damon_for_each_target(t, ctx) { + damon_for_each_region(r, t) + sz += r->ar.end - r->ar.start; + } + + if (ctx->min_nr_regions) + sz /= ctx->min_nr_regions; + if (sz < MIN_REGION) + sz = MIN_REGION; + + return sz; +} + /* * Functions for DAMON core logics and features */ @@ -226,6 +246,145 @@ static void kdamond_reset_aggregated(struct damon_ctx *c) } } +#define sz_damon_region(r) (r->ar.end - r->ar.start) + +/* + * Merge two adjacent regions into one region + */ +static void damon_merge_two_regions(struct damon_region *l, + struct damon_region *r) +{ + l->nr_accesses = (l->nr_accesses * sz_damon_region(l) + + r->nr_accesses * sz_damon_region(r)) / + (sz_damon_region(l) + sz_damon_region(r)); + l->ar.end = r->ar.end; + damon_destroy_region(r); +} + +#define diff_of(a, b) (a > b ? a - b : b - a) + +/* + * Merge adjacent regions having similar access frequencies + * + * t target affected by this merge operation + * thres '->nr_accesses' diff threshold for the merge + * sz_limit size upper limit of each region + */ +static void damon_merge_regions_of(struct damon_target *t, unsigned int thres, + unsigned long sz_limit) +{ + struct damon_region *r, *prev = NULL, *next; + + damon_for_each_region_safe(r, next, t) { + if (prev && prev->ar.end == r->ar.start && + diff_of(prev->nr_accesses, r->nr_accesses) <= thres && + sz_damon_region(prev) + sz_damon_region(r) <= sz_limit) + damon_merge_two_regions(prev, r); + else + prev = r; + } +} + +/* + * Merge adjacent regions having similar access frequencies + * + * threshold '->nr_accesses' diff threshold for the merge + * sz_limit size upper limit of each region + * + * This function merges monitoring target regions which are adjacent and their + * access frequencies are similar. This is for minimizing the monitoring + * overhead under the dynamically changeable access pattern. If a merge was + * unnecessarily made, later 'kdamond_split_regions()' will revert it. + */ +static void kdamond_merge_regions(struct damon_ctx *c, unsigned int threshold, + unsigned long sz_limit) +{ + struct damon_target *t; + + damon_for_each_target(t, c) + damon_merge_regions_of(t, threshold, sz_limit); +} + +/* + * Split a region in two + * + * r the region to be split + * sz_r size of the first sub-region that will be made + */ +static void damon_split_region_at(struct damon_ctx *ctx, + struct damon_region *r, unsigned long sz_r) +{ + struct damon_region *new; + + new = damon_new_region(r->ar.start + sz_r, r->ar.end); + r->ar.end = new->ar.start; + + damon_insert_region(new, r, damon_next_region(r)); +} + +/* Split every region in the given target into 'nr_subs' regions */ +static void damon_split_regions_of(struct damon_ctx *ctx, + struct damon_target *t, int nr_subs) +{ + struct damon_region *r, *next; + unsigned long sz_region, sz_sub = 0; + int i; + + damon_for_each_region_safe(r, next, t) { + sz_region = r->ar.end - r->ar.start; + + for (i = 0; i < nr_subs - 1 && + sz_region > 2 * MIN_REGION; i++) { + /* + * Randomly select size of left sub-region to be at + * least 10 percent and at most 90% of original region + */ + sz_sub = ALIGN_DOWN(damon_rand(1, 10) * + sz_region / 10, MIN_REGION); + /* Do not allow blank region */ + if (sz_sub == 0 || sz_sub >= sz_region) + continue; + + damon_split_region_at(ctx, r, sz_sub); + sz_region = sz_sub; + } + } +} + +/* + * Split every target region into randomly-sized small regions + * + * This function splits every target region into random-sized small regions if + * current total number of the regions is equal or smaller than half of the + * user-specified maximum number of regions. This is for maximizing the + * monitoring accuracy under the dynamically changeable access patterns. If a + * split was unnecessarily made, later 'kdamond_merge_regions()' will revert + * it. + */ +static void kdamond_split_regions(struct damon_ctx *ctx) +{ + struct damon_target *t; + unsigned int nr_regions = 0; + static unsigned int last_nr_regions; + int nr_subregions = 2; + + damon_for_each_target(t, ctx) + nr_regions += nr_damon_regions(t); + + if (nr_regions > ctx->max_nr_regions / 2) + return; + + /* Maybe the middle of the region has different access frequency */ + if (last_nr_regions == nr_regions && + nr_regions < ctx->max_nr_regions / 3) + nr_subregions = 3; + + damon_for_each_target(t, ctx) + damon_split_regions_of(ctx, t, nr_subregions); + + last_nr_regions = nr_regions; +} + /* * Check whether current monitoring should be stopped * @@ -264,10 +423,14 @@ static int kdamond_fn(void *data) struct damon_ctx *ctx = (struct damon_ctx *)data; struct damon_target *t; struct damon_region *r, *next; + unsigned int max_nr_accesses = 0; + unsigned long sz_limit = 0; pr_info("kdamond (%d) starts\n", ctx->kdamond->pid); if (ctx->init_target_regions) ctx->init_target_regions(ctx); + sz_limit = damon_region_sz_limit(ctx); + while (!kdamond_need_stop(ctx)) { if (ctx->prepare_access_checks) ctx->prepare_access_checks(ctx); @@ -277,14 +440,16 @@ static int kdamond_fn(void *data) usleep_range(ctx->sample_interval, ctx->sample_interval + 1); if (ctx->check_accesses) - ctx->check_accesses(ctx); + max_nr_accesses = ctx->check_accesses(ctx); if (kdamond_aggregate_interval_passed(ctx)) { if (ctx->aggregate_cb) ctx->aggregate_cb(ctx); + kdamond_merge_regions(ctx, max_nr_accesses / 10, + sz_limit); kdamond_reset_aggregated(ctx); + kdamond_split_regions(ctx); } - } damon_for_each_target(t, ctx) { damon_for_each_region_safe(r, next, t) @@ -460,25 +625,33 @@ int damon_set_targets(struct damon_ctx *ctx, * @ctx: monitoring context * @sample_int: time interval between samplings * @aggr_int: time interval between aggregations - * @nr_reg: number of regions + * @min_nr_reg: minimal number of regions + * @max_nr_reg: maximum number of regions * * This function should not be called while the kdamond is running. * Every time interval is in micro-seconds. * * Return: 0 on success, negative error code otherwise. */ -int damon_set_attrs(struct damon_ctx *ctx, unsigned long sample_int, - unsigned long aggr_int, unsigned long nr_reg) +int damon_set_attrs(struct damon_ctx *ctx, + unsigned long sample_int, unsigned long aggr_int, + unsigned long min_nr_reg, unsigned long max_nr_reg) { - if (nr_reg < 3) { - pr_err("nr_regions (%lu) must be at least 3\n", - nr_reg); + if (min_nr_reg < 3) { + pr_err("min_nr_regions (%lu) must be at least 3\n", + min_nr_reg); + return -EINVAL; + } + if (min_nr_reg > max_nr_reg) { + pr_err("invalid nr_regions. min (%lu) > max (%lu)\n", + min_nr_reg, max_nr_reg); return -EINVAL; } ctx->sample_interval = sample_int; ctx->aggr_interval = aggr_int; - ctx->nr_regions = nr_reg; + ctx->min_nr_regions = min_nr_reg; + ctx->max_nr_regions = max_nr_reg; return 0; } From patchwork Mon Aug 17 10:51:26 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: SeongJae Park X-Patchwork-Id: 11717991 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 BDA3213A4 for ; Mon, 17 Aug 2020 10:54:14 +0000 (UTC) Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by mail.kernel.org (Postfix) with ESMTP id 7D92720758 for ; Mon, 17 Aug 2020 10:54:14 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (1024-bit key) header.d=amazon.com header.i=@amazon.com header.b="VzI4/XwS" DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org 7D92720758 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 BE8826B0007; Mon, 17 Aug 2020 06:54:13 -0400 (EDT) Delivered-To: linux-mm-outgoing@kvack.org Received: by kanga.kvack.org (Postfix, from userid 40) id B71C16B000A; Mon, 17 Aug 2020 06:54:13 -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 A13B76B000C; Mon, 17 Aug 2020 06:54:13 -0400 (EDT) X-Original-To: linux-mm@kvack.org X-Delivered-To: linux-mm@kvack.org Received: from forelay.hostedemail.com (smtprelay0084.hostedemail.com [216.40.44.84]) by kanga.kvack.org (Postfix) with ESMTP id 870256B0007 for ; Mon, 17 Aug 2020 06:54:13 -0400 (EDT) Received: from smtpin26.hostedemail.com (10.5.19.251.rfc1918.com [10.5.19.251]) by forelay05.hostedemail.com (Postfix) with ESMTP id 3AE46181AEF3C for ; Mon, 17 Aug 2020 10:54:13 +0000 (UTC) X-FDA: 77159751186.26.sofa39_080046427016 Received: from filter.hostedemail.com (10.5.16.251.rfc1918.com [10.5.16.251]) by smtpin26.hostedemail.com (Postfix) with ESMTP id 03B721804B65C for ; Mon, 17 Aug 2020 10:54:12 +0000 (UTC) X-Spam-Summary: 1,0,0,,d41d8cd98f00b204,prvs=491cff689=sjpark@amazon.com,,RULES_HIT:30003:30012:30034:30046:30054:30064:30070:30075,0,RBL:52.95.48.154:@amazon.com:.lbl8.mailshell.net-62.18.0.100 64.10.201.10;04ygmph7ag7dgz4g5gbbziuxct1mzypczbpemn4hw8ai1b1yba4oghbw57nk5m8.y6154hfkznmkze3ta6j1zhnuyhus4kojrpen7f4s9npnwurf917u16j4izirbt8.n-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: sofa39_080046427016 X-Filterd-Recvd-Size: 10099 Received: from smtp-fw-6001.amazon.com (smtp-fw-6001.amazon.com [52.95.48.154]) by imf39.hostedemail.com (Postfix) with ESMTP for ; Mon, 17 Aug 2020 10:54:12 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=amazon.com; i=@amazon.com; q=dns/txt; s=amazon201209; t=1597661652; x=1629197652; h=from:to:cc:subject:date:message-id:in-reply-to: references:mime-version; bh=LBkVD+Wxv/M9aVrPwb/7QYNuHeSGbLtCTunoYImZEDw=; b=VzI4/XwSedPOq3+pmKeLErOsF1WSFoRd+N41PM3fiiVXMhGg88ORUNDT xikAbLs128UUfzlIPQoHcQC+hJqTXatxIq1VGWXIJ8Ygj2Kv8/wEiyuxR SqdRNsaSJYiIkvMvPkqjMAJ+1JDfY7ENiXbo3o/YNC4lqOgvjsq0eIhSm M=; X-IronPort-AV: E=Sophos;i="5.76,322,1592870400"; d="scan'208";a="49617019" Received: from iad12-co-svc-p1-lb1-vlan3.amazon.com (HELO email-inbound-relay-2a-90c42d1d.us-west-2.amazon.com) ([10.43.8.6]) by smtp-border-fw-out-6001.iad6.amazon.com with ESMTP; 17 Aug 2020 10:53:55 +0000 Received: from EX13MTAUEA001.ant.amazon.com (pdx4-ws-svc-p6-lb7-vlan3.pdx.amazon.com [10.170.41.166]) by email-inbound-relay-2a-90c42d1d.us-west-2.amazon.com (Postfix) with ESMTPS id B6162A18C5; Mon, 17 Aug 2020 10:53:52 +0000 (UTC) Received: from EX13D31EUA001.ant.amazon.com (10.43.165.15) by EX13MTAUEA001.ant.amazon.com (10.43.61.82) with Microsoft SMTP Server (TLS) id 15.0.1497.2; Mon, 17 Aug 2020 10:53:51 +0000 Received: from u3f2cd687b01c55.ant.amazon.com (10.43.160.192) by EX13D31EUA001.ant.amazon.com (10.43.165.15) with Microsoft SMTP Server (TLS) id 15.0.1497.2; Mon, 17 Aug 2020 10:53:33 +0000 From: SeongJae Park To: CC: SeongJae Park , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , Subject: [PATCH v20 04/15] mm/damon: Track dynamic monitoring target regions update Date: Mon, 17 Aug 2020 12:51:26 +0200 Message-ID: <20200817105137.19296-5-sjpark@amazon.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20200817105137.19296-1-sjpark@amazon.com> References: <20200817105137.19296-1-sjpark@amazon.com> MIME-Version: 1.0 X-Originating-IP: [10.43.160.192] X-ClientProxiedBy: EX13D02UWC004.ant.amazon.com (10.43.162.236) To EX13D31EUA001.ant.amazon.com (10.43.165.15) X-Rspamd-Queue-Id: 03B721804B65C X-Spamd-Result: default: False [0.00 / 100.00] X-Rspamd-Server: rspam02 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 The monitoring target address range can be dynamically changed. For example, virtual memory could be dynamically mapped and unmapped. Physical memory could be hot-plugged. As the changes could be quite frequent in some cases, DAMON checks the dynamic memory mapping changes and applies it to the abstracted target area only for each of a user-specified time interval, ``regions update interval``. Signed-off-by: SeongJae Park Reviewed-by: Leonard Foerster --- include/linux/damon.h | 20 +++++++++++++++----- mm/damon.c | 23 +++++++++++++++++++++-- 2 files changed, 36 insertions(+), 7 deletions(-) diff --git a/include/linux/damon.h b/include/linux/damon.h index 708775a36be3..65533be91735 100644 --- a/include/linux/damon.h +++ b/include/linux/damon.h @@ -64,13 +64,16 @@ struct damon_target { * * @sample_interval: The time between access samplings. * @aggr_interval: The time between monitor results aggregations. + * @regions_update_interval: The time between monitor regions updates. * @min_nr_regions: The minimum number of monitoring regions. * @max_nr_regions: The maximum number of monitoring regions. * * For each @sample_interval, DAMON checks whether each region is accessed or * not. It aggregates and keeps the access information (number of accesses to - * each region) for @aggr_interval time. All time intervals are in - * micro-seconds. + * each region) for @aggr_interval time. DAMON also checks whether the target + * memory regions need update (e.g., by ``mmap()`` calls from the application, + * in case of virtual memory monitoring) and applies the changes for each + * @regions_update_interval. All time intervals are in micro-seconds. * * @kdamond: Kernel thread who does the monitoring. * @kdamond_stop: Notifies whether kdamond should stop. @@ -94,6 +97,7 @@ struct damon_target { * @targets_list: Head of monitoring targets (&damon_target) list. * * @init_target_regions: Constructs initial monitoring target regions. + * @update_target_regions: Updates monitoring target regions. * @prepare_access_checks: Prepares next access check of target regions. * @check_accesses: Checks the access of target regions. * @target_valid: Determine if the target is valid. @@ -104,12 +108,15 @@ struct damon_target { * DAMON can be extended for various address spaces by users. For this, users * can register the target address space dependent low level functions for * their usecases via the callback pointers of the context. The monitoring - * thread calls @init_target_regions before starting the monitoring, and + * thread calls @init_target_regions before starting the monitoring, + * @update_target_regions for each @regions_update_interval, and * @prepare_access_checks, @check_accesses, and @target_valid for each * @sample_interval. * * @init_target_regions should construct proper monitoring target regions and * link those to the DAMON context struct. + * @update_target_regions should update the monitoring target regions for + * current status. * @prepare_access_checks should manipulate the monitoring regions to be * prepare for the next access check. * @check_accesses should check the accesses to each region that made after the @@ -128,10 +135,12 @@ struct damon_target { struct damon_ctx { unsigned long sample_interval; unsigned long aggr_interval; + unsigned long regions_update_interval; unsigned long min_nr_regions; unsigned long max_nr_regions; struct timespec64 last_aggregation; + struct timespec64 last_regions_update; struct task_struct *kdamond; bool kdamond_stop; @@ -141,6 +150,7 @@ struct damon_ctx { /* callbacks */ void (*init_target_regions)(struct damon_ctx *context); + void (*update_target_regions)(struct damon_ctx *context); void (*prepare_access_checks)(struct damon_ctx *context); unsigned int (*check_accesses)(struct damon_ctx *context); bool (*target_valid)(struct damon_target *target); @@ -151,8 +161,8 @@ struct damon_ctx { int damon_set_targets(struct damon_ctx *ctx, unsigned long *ids, ssize_t nr_ids); -int damon_set_attrs(struct damon_ctx *ctx, - unsigned long sample_int, unsigned long aggr_int, +int damon_set_attrs(struct damon_ctx *ctx, unsigned long sample_int, + unsigned long aggr_int, unsigned long regions_update_int, unsigned long min_nr_reg, unsigned long max_nr_reg); int damon_start(struct damon_ctx *ctxs, int nr_ctxs); int damon_stop(struct damon_ctx *ctxs, int nr_ctxs); diff --git a/mm/damon.c b/mm/damon.c index 13b17074d411..59d0b59858ae 100644 --- a/mm/damon.c +++ b/mm/damon.c @@ -385,6 +385,17 @@ static void kdamond_split_regions(struct damon_ctx *ctx) last_nr_regions = nr_regions; } +/* + * Check whether it is time to check and apply the target monitoring regions + * + * Returns true if it is. + */ +static bool kdamond_need_update_regions(struct damon_ctx *ctx) +{ + return damon_check_reset_time_interval(&ctx->last_regions_update, + ctx->regions_update_interval); +} + /* * Check whether current monitoring should be stopped * @@ -450,6 +461,12 @@ static int kdamond_fn(void *data) kdamond_reset_aggregated(ctx); kdamond_split_regions(ctx); } + + if (kdamond_need_update_regions(ctx)) { + if (ctx->update_target_regions) + ctx->update_target_regions(ctx); + sz_limit = damon_region_sz_limit(ctx); + } } damon_for_each_target(t, ctx) { damon_for_each_region_safe(r, next, t) @@ -624,6 +641,7 @@ int damon_set_targets(struct damon_ctx *ctx, * damon_set_attrs() - Set attributes for the monitoring. * @ctx: monitoring context * @sample_int: time interval between samplings + * @regions_update_int: time interval between target regions update * @aggr_int: time interval between aggregations * @min_nr_reg: minimal number of regions * @max_nr_reg: maximum number of regions @@ -633,8 +651,8 @@ int damon_set_targets(struct damon_ctx *ctx, * * Return: 0 on success, negative error code otherwise. */ -int damon_set_attrs(struct damon_ctx *ctx, - unsigned long sample_int, unsigned long aggr_int, +int damon_set_attrs(struct damon_ctx *ctx, unsigned long sample_int, + unsigned long aggr_int, unsigned long regions_update_int, unsigned long min_nr_reg, unsigned long max_nr_reg) { if (min_nr_reg < 3) { @@ -650,6 +668,7 @@ int damon_set_attrs(struct damon_ctx *ctx, ctx->sample_interval = sample_int; ctx->aggr_interval = aggr_int; + ctx->regions_update_interval = regions_update_int; ctx->min_nr_regions = min_nr_reg; ctx->max_nr_regions = max_nr_reg; From patchwork Mon Aug 17 10:51:27 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: SeongJae Park X-Patchwork-Id: 11717993 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 0B024109B for ; Mon, 17 Aug 2020 10:54:28 +0000 (UTC) Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by mail.kernel.org (Postfix) with ESMTP id BDFDE207DF for ; Mon, 17 Aug 2020 10:54:27 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (1024-bit key) header.d=amazon.com header.i=@amazon.com header.b="agWterXD" DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org BDFDE207DF 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 029586B0008; Mon, 17 Aug 2020 06:54:27 -0400 (EDT) Delivered-To: linux-mm-outgoing@kvack.org Received: by kanga.kvack.org (Postfix, from userid 40) id F1ACC6B000A; Mon, 17 Aug 2020 06:54:26 -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 DE2B36B000C; Mon, 17 Aug 2020 06:54:26 -0400 (EDT) X-Original-To: linux-mm@kvack.org X-Delivered-To: linux-mm@kvack.org Received: from forelay.hostedemail.com (smtprelay0250.hostedemail.com [216.40.44.250]) by kanga.kvack.org (Postfix) with ESMTP id C35376B0008 for ; Mon, 17 Aug 2020 06:54:26 -0400 (EDT) Received: from smtpin20.hostedemail.com (10.5.19.251.rfc1918.com [10.5.19.251]) by forelay03.hostedemail.com (Postfix) with ESMTP id 893C1824556B for ; Mon, 17 Aug 2020 10:54:26 +0000 (UTC) X-FDA: 77159751732.20.toad84_501765927016 Received: from filter.hostedemail.com (10.5.16.251.rfc1918.com [10.5.16.251]) by smtpin20.hostedemail.com (Postfix) with ESMTP id 4DAFE180C07AB for ; Mon, 17 Aug 2020 10:54:26 +0000 (UTC) X-Spam-Summary: 1,0,0,,d41d8cd98f00b204,prvs=491cff689=sjpark@amazon.com,,RULES_HIT:30003:30005:30029:30045:30051:30054:30064:30075,0,RBL:207.171.190.10:@amazon.com:.lbl8.mailshell.net-66.10.201.10 62.18.0.100;04yfx3m8ewm5ymqg6gj5sxjb34pdpoc4ehf6ws9w8uuhwqcsgbz7ay8t9xqu65r.7ee47nnb9xijiotnjtsg9hu57486ky75npg6yzi49dziws35u1hm5sbtu5qjqwt.k-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:76,LUA_SUMMARY:none X-HE-Tag: toad84_501765927016 X-Filterd-Recvd-Size: 9748 Received: from smtp-fw-33001.amazon.com (smtp-fw-33001.amazon.com [207.171.190.10]) by imf46.hostedemail.com (Postfix) with ESMTP for ; Mon, 17 Aug 2020 10:54:25 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=amazon.com; i=@amazon.com; q=dns/txt; s=amazon201209; t=1597661665; x=1629197665; h=from:to:cc:subject:date:message-id:in-reply-to: references:mime-version; bh=7xwibYs3UTgv+ydCDCzKAP/73v9ORCmfR0/3U8RJ7hA=; b=agWterXDQpiMfYNVSjZmS2tuJ/7rKs75YcKbTAbLmIkl8Narn1h7pcCA URz3WJlTzbSeaj3/wF7ZeLK/9RfamCqDCSepDhqOkVko1R56MbGjFM+tT X4x8+tk2vjr3N7FXtXnkAbrIKqztSEAQvHG+yFOcSE8UhAzy+UHCeW4+w I=; X-IronPort-AV: E=Sophos;i="5.76,322,1592870400"; d="scan'208";a="67283877" Received: from sea32-co-svc-lb4-vlan3.sea.corp.amazon.com (HELO email-inbound-relay-1e-97fdccfd.us-east-1.amazon.com) ([10.47.23.38]) by smtp-border-fw-out-33001.sea14.amazon.com with ESMTP; 17 Aug 2020 10:54:22 +0000 Received: from EX13MTAUEA002.ant.amazon.com (iad55-ws-svc-p15-lb9-vlan2.iad.amazon.com [10.40.159.162]) by email-inbound-relay-1e-97fdccfd.us-east-1.amazon.com (Postfix) with ESMTPS id 9713FA2215; Mon, 17 Aug 2020 10:54:10 +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; Mon, 17 Aug 2020 10:54:09 +0000 Received: from u3f2cd687b01c55.ant.amazon.com (10.43.160.192) by EX13D31EUA001.ant.amazon.com (10.43.165.15) with Microsoft SMTP Server (TLS) id 15.0.1497.2; Mon, 17 Aug 2020 10:53:53 +0000 From: SeongJae Park To: CC: SeongJae Park , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , Subject: [PATCH v20 05/15] mm/idle_page_tracking: Make PG_(idle|young) reusable Date: Mon, 17 Aug 2020 12:51:27 +0200 Message-ID: <20200817105137.19296-6-sjpark@amazon.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20200817105137.19296-1-sjpark@amazon.com> References: <20200817105137.19296-1-sjpark@amazon.com> MIME-Version: 1.0 X-Originating-IP: [10.43.160.192] X-ClientProxiedBy: EX13D02UWC004.ant.amazon.com (10.43.162.236) To EX13D31EUA001.ant.amazon.com (10.43.165.15) X-Rspamd-Queue-Id: 4DAFE180C07AB X-Spamd-Result: default: False [0.00 / 100.00] X-Rspamd-Server: rspam03 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 PG_idle and PG_young allows the two PTE Accessed bit users, IDLE_PAGE_TRACKING and the reclaim logic concurrently work while don't interfere each other. That is, when they need to clear the Accessed bit, they set PG_young and PG_idle to represent the previous state of the bit, respectively. And when they need to read the bit, if the bit is cleared, they further read the PG_young and PG_idle, respectively, to know whether the other has cleared the bit meanwhile or not. We could add another page flag and extend the mechanism to use the flag if we need to add another concurrent PTE Accessed bit user subsystem. However, it would be only waste the space. Instead, if the new subsystem is mutually exclusive with IDLE_PAGE_TRACKING, it could simply reuse the PG_idle flag. However, it's impossible because the flags are dependent on IDLE_PAGE_TRACKING. To allow such reuse of the flags, this commit separates the PG_young and PG_idle flag logic from IDLE_PAGE_TRACKING and introduces new kernel config, 'PAGE_IDLE_FLAG'. Hence, if !IDLE_PAGE_TRACKING and IDLE_PAGE_FLAG, a new subsystem would be able to reuse PG_idle. In the next commit, DAMON's reference implementation of the virtual memory address space monitoring primitives will use it. Signed-off-by: SeongJae Park --- include/linux/page-flags.h | 4 ++-- include/linux/page_ext.h | 2 +- include/linux/page_idle.h | 6 +++--- include/trace/events/mmflags.h | 2 +- mm/Kconfig | 8 ++++++++ mm/page_ext.c | 12 +++++++++++- mm/page_idle.c | 10 ---------- 7 files changed, 26 insertions(+), 18 deletions(-) diff --git a/include/linux/page-flags.h b/include/linux/page-flags.h index 6be1aa559b1e..7736d290bb61 100644 --- a/include/linux/page-flags.h +++ b/include/linux/page-flags.h @@ -132,7 +132,7 @@ enum pageflags { #ifdef CONFIG_MEMORY_FAILURE PG_hwpoison, /* hardware poisoned page. Don't touch */ #endif -#if defined(CONFIG_IDLE_PAGE_TRACKING) && defined(CONFIG_64BIT) +#if defined(CONFIG_PAGE_IDLE_FLAG) && defined(CONFIG_64BIT) PG_young, PG_idle, #endif @@ -432,7 +432,7 @@ static inline bool set_hwpoison_free_buddy_page(struct page *page) #define __PG_HWPOISON 0 #endif -#if defined(CONFIG_IDLE_PAGE_TRACKING) && defined(CONFIG_64BIT) +#if defined(CONFIG_PAGE_IDLE_FLAG) && defined(CONFIG_64BIT) TESTPAGEFLAG(Young, young, PF_ANY) SETPAGEFLAG(Young, young, PF_ANY) TESTCLEARFLAG(Young, young, PF_ANY) diff --git a/include/linux/page_ext.h b/include/linux/page_ext.h index cfce186f0c4e..c9cbc9756011 100644 --- a/include/linux/page_ext.h +++ b/include/linux/page_ext.h @@ -19,7 +19,7 @@ struct page_ext_operations { enum page_ext_flags { PAGE_EXT_OWNER, PAGE_EXT_OWNER_ALLOCATED, -#if defined(CONFIG_IDLE_PAGE_TRACKING) && !defined(CONFIG_64BIT) +#if defined(CONFIG_PAGE_IDLE_FLAG) && !defined(CONFIG_64BIT) PAGE_EXT_YOUNG, PAGE_EXT_IDLE, #endif diff --git a/include/linux/page_idle.h b/include/linux/page_idle.h index 1e894d34bdce..d8a6aecf99cb 100644 --- a/include/linux/page_idle.h +++ b/include/linux/page_idle.h @@ -6,7 +6,7 @@ #include #include -#ifdef CONFIG_IDLE_PAGE_TRACKING +#ifdef CONFIG_PAGE_IDLE_FLAG #ifdef CONFIG_64BIT static inline bool page_is_young(struct page *page) @@ -106,7 +106,7 @@ static inline void clear_page_idle(struct page *page) } #endif /* CONFIG_64BIT */ -#else /* !CONFIG_IDLE_PAGE_TRACKING */ +#else /* !CONFIG_PAGE_IDLE_FLAG */ static inline bool page_is_young(struct page *page) { @@ -135,6 +135,6 @@ static inline void clear_page_idle(struct page *page) { } -#endif /* CONFIG_IDLE_PAGE_TRACKING */ +#endif /* CONFIG_PAGE_IDLE_FLAG */ #endif /* _LINUX_MM_PAGE_IDLE_H */ diff --git a/include/trace/events/mmflags.h b/include/trace/events/mmflags.h index 5fb752034386..4d182c32071b 100644 --- a/include/trace/events/mmflags.h +++ b/include/trace/events/mmflags.h @@ -73,7 +73,7 @@ #define IF_HAVE_PG_HWPOISON(flag,string) #endif -#if defined(CONFIG_IDLE_PAGE_TRACKING) && defined(CONFIG_64BIT) +#if defined(CONFIG_PAGE_IDLE_FLAG) && defined(CONFIG_64BIT) #define IF_HAVE_PG_IDLE(flag,string) ,{1UL << flag, string} #else #define IF_HAVE_PG_IDLE(flag,string) diff --git a/mm/Kconfig b/mm/Kconfig index a99d755d67d3..8b1dacc60a8e 100644 --- a/mm/Kconfig +++ b/mm/Kconfig @@ -765,10 +765,18 @@ config DEFERRED_STRUCT_PAGE_INIT lifetime of the system until these kthreads finish the initialisation. +config PAGE_IDLE_FLAG + bool "Add PG_idle and PG_young flags" + help + This feature adds PG_idle and PG_young flags in 'struct page'. PTE + Accessed bit writers can set the state of the bit in the flags to let + other PTE Accessed bit readers don't disturbed. + config IDLE_PAGE_TRACKING bool "Enable idle page tracking" depends on SYSFS && MMU select PAGE_EXTENSION if !64BIT + select PAGE_IDLE_FLAG help This feature allows to estimate the amount of user pages that have not been touched during a given period of time. This information can diff --git a/mm/page_ext.c b/mm/page_ext.c index a3616f7a0e9e..f9a6ff65ac0a 100644 --- a/mm/page_ext.c +++ b/mm/page_ext.c @@ -58,11 +58,21 @@ * can utilize this callback to initialize the state of it correctly. */ +#if defined(CONFIG_PAGE_IDLE_FLAG) && !defined(CONFIG_64BIT) +static bool need_page_idle(void) +{ + return true; +} +struct page_ext_operations page_idle_ops = { + .need = need_page_idle, +}; +#endif + static struct page_ext_operations *page_ext_ops[] = { #ifdef CONFIG_PAGE_OWNER &page_owner_ops, #endif -#if defined(CONFIG_IDLE_PAGE_TRACKING) && !defined(CONFIG_64BIT) +#if defined(CONFIG_PAGE_IDLE_FLAG) && !defined(CONFIG_64BIT) &page_idle_ops, #endif }; diff --git a/mm/page_idle.c b/mm/page_idle.c index 057c61df12db..144fb4ed961d 100644 --- a/mm/page_idle.c +++ b/mm/page_idle.c @@ -211,16 +211,6 @@ static const struct attribute_group page_idle_attr_group = { .name = "page_idle", }; -#ifndef CONFIG_64BIT -static bool need_page_idle(void) -{ - return true; -} -struct page_ext_operations page_idle_ops = { - .need = need_page_idle, -}; -#endif - static int __init page_idle_init(void) { int err; From patchwork Mon Aug 17 10:51:28 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: SeongJae Park X-Patchwork-Id: 11717995 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 B770B109B for ; Mon, 17 Aug 2020 10:54:45 +0000 (UTC) Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by mail.kernel.org (Postfix) with ESMTP id 60A5520758 for ; Mon, 17 Aug 2020 10:54:45 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (1024-bit key) header.d=amazon.com header.i=@amazon.com header.b="mtfOOlJ/" DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org 60A5520758 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 88C896B000A; Mon, 17 Aug 2020 06:54:44 -0400 (EDT) Delivered-To: linux-mm-outgoing@kvack.org Received: by kanga.kvack.org (Postfix, from userid 40) id 815066B000C; Mon, 17 Aug 2020 06:54:44 -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 690636B000D; Mon, 17 Aug 2020 06:54:44 -0400 (EDT) X-Original-To: linux-mm@kvack.org X-Delivered-To: linux-mm@kvack.org Received: from forelay.hostedemail.com (smtprelay0030.hostedemail.com [216.40.44.30]) by kanga.kvack.org (Postfix) with ESMTP id 48FD16B000A for ; Mon, 17 Aug 2020 06:54:44 -0400 (EDT) Received: from smtpin22.hostedemail.com (10.5.19.251.rfc1918.com [10.5.19.251]) by forelay05.hostedemail.com (Postfix) with ESMTP id F1FF4181AEF3C for ; Mon, 17 Aug 2020 10:54:43 +0000 (UTC) X-FDA: 77159752488.22.eggs94_201138e27016 Received: from filter.hostedemail.com (10.5.16.251.rfc1918.com [10.5.16.251]) by smtpin22.hostedemail.com (Postfix) with ESMTP id BA98A18037368 for ; Mon, 17 Aug 2020 10:54:43 +0000 (UTC) X-Spam-Summary: 1,0,0,,d41d8cd98f00b204,prvs=491cff689=sjpark@amazon.com,,RULES_HIT:30003:30012:30034:30051:30054:30056:30064:30070:30071:30075:30080:30090,0,RBL:52.95.49.90:@amazon.com:.lbl8.mailshell.net-62.18.0.100 64.10.201.10;04y88ti734edye9otn1fxa3r1p65mycaws9rbc63tz9skk58keqbocsz1jybr39.pmgskrpfrs3iza5dr8e917q3qxqtjuqmuqoos9cur9autkttc3yahi8rcq1rkhr.n-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:23,LUA_SUMMARY:none X-HE-Tag: eggs94_201138e27016 X-Filterd-Recvd-Size: 23623 Received: from smtp-fw-6002.amazon.com (smtp-fw-6002.amazon.com [52.95.49.90]) by imf29.hostedemail.com (Postfix) with ESMTP for ; Mon, 17 Aug 2020 10:54:43 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=amazon.com; i=@amazon.com; q=dns/txt; s=amazon201209; t=1597661683; x=1629197683; h=from:to:cc:subject:date:message-id:in-reply-to: references:mime-version; bh=PO9R3LoCDw3ZzoW+4R2EhnjoBSCW00iS2IT/7/rIwM4=; b=mtfOOlJ/TdySgxG6vPPiO0pFET4GFnVHGzocxB5wzLkgYZ+Rd3HtfQch 5nUCNjdUt9Bd/ivM4b0OMz50ry5g5U6nA23F3vcFchfrd+qcn8sXBluzx UnddzM3Jn754+2qSC3GN1MIC2y9XiGKAAkTwAen9Xk+yt893QCpEwv6hg 0=; X-IronPort-AV: E=Sophos;i="5.76,322,1592870400"; d="scan'208";a="48182095" Received: from iad12-co-svc-p1-lb1-vlan3.amazon.com (HELO email-inbound-relay-2a-53356bf6.us-west-2.amazon.com) ([10.43.8.6]) by smtp-border-fw-out-6002.iad6.amazon.com with ESMTP; 17 Aug 2020 10:54:39 +0000 Received: from EX13MTAUEA001.ant.amazon.com (pdx4-ws-svc-p6-lb7-vlan2.pdx.amazon.com [10.170.41.162]) by email-inbound-relay-2a-53356bf6.us-west-2.amazon.com (Postfix) with ESMTPS id 8DAD7A1F5F; Mon, 17 Aug 2020 10:54:36 +0000 (UTC) Received: from EX13D31EUA001.ant.amazon.com (10.43.165.15) by EX13MTAUEA001.ant.amazon.com (10.43.61.82) with Microsoft SMTP Server (TLS) id 15.0.1497.2; Mon, 17 Aug 2020 10:54:35 +0000 Received: from u3f2cd687b01c55.ant.amazon.com (10.43.160.192) by EX13D31EUA001.ant.amazon.com (10.43.165.15) with Microsoft SMTP Server (TLS) id 15.0.1497.2; Mon, 17 Aug 2020 10:54:18 +0000 From: SeongJae Park To: CC: SeongJae Park , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , Subject: [PATCH v20 06/15] mm/damon: Implement callbacks for the virtual memory address spaces Date: Mon, 17 Aug 2020 12:51:28 +0200 Message-ID: <20200817105137.19296-7-sjpark@amazon.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20200817105137.19296-1-sjpark@amazon.com> References: <20200817105137.19296-1-sjpark@amazon.com> MIME-Version: 1.0 X-Originating-IP: [10.43.160.192] X-ClientProxiedBy: EX13D02UWC004.ant.amazon.com (10.43.162.236) To EX13D31EUA001.ant.amazon.com (10.43.165.15) X-Rspamd-Queue-Id: BA98A18037368 X-Spamd-Result: default: False [0.00 / 100.00] X-Rspamd-Server: rspam04 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 This commit introduces a reference implementation of the address space specific low level primitives for the virtual address space, so that users of DAMON can easily monitor the data accesses on virtual address spaces of specific processes by simply configuring the implementation to be used by DAMON. The low level primitives for the fundamental access monitoring are defined in two parts: 1. Identification of the monitoring target address range for the address space. 2. Access check of specific address range in the target space. The reference implementation for the virtual address space provided by this commit is designed as below. PTE Accessed-bit Based Access Check ----------------------------------- The implementation uses PTE Accessed-bit for basic access checks. That is, it clears the bit for next sampling target page and checks whether it set again after one sampling period. This could disturb other kernel subsystems using the Accessed bits, namely Idle page tracking and the reclaim logic. To avoid such disturbances, DAMON makes it mutually exclusive with Idle page tracking and uses ``PG_idle`` and ``PG_young`` page flags to solve the conflict with the reclaim logics, as Idle page tracking does. VMA-based Target Address Range Construction ------------------------------------------- Only small parts in the super-huge virtual address space of the processes are mapped to physical memory and accessed. Thus, tracking the unmapped address regions is just wasteful. However, because DAMON can deal with some level of noise using the adaptive regions adjustment mechanism, tracking every mapping is not strictly required but could even incur a high overhead in some cases. That said, too huge unmapped areas inside the monitoring target should be removed to not take the time for the adaptive mechanism. For the reason, this implementation converts the complex mappings to three distinct regions that cover every mapped area of the address space. Also, the two gaps between the three regions are the two biggest unmapped areas in the given address space. The two biggest unmapped areas would be the gap between the heap and the uppermost mmap()-ed region, and the gap between the lowermost mmap()-ed region and the stack in most of the cases. Because these gaps are exceptionally huge in usual address spacees, excluding these will be sufficient to make a reasonable trade-off. Below shows this in detail:: (small mmap()-ed regions and munmap()-ed regions) Signed-off-by: SeongJae Park Reviewed-by: Leonard Foerster --- include/linux/damon.h | 8 + mm/Kconfig | 3 + mm/damon.c | 552 ++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 563 insertions(+) diff --git a/include/linux/damon.h b/include/linux/damon.h index 65533be91735..945eb9259acf 100644 --- a/include/linux/damon.h +++ b/include/linux/damon.h @@ -159,6 +159,14 @@ struct damon_ctx { void (*aggregate_cb)(struct damon_ctx *context); }; +/* Reference callback implementations for virtual memory */ +void kdamond_init_vm_regions(struct damon_ctx *ctx); +void kdamond_update_vm_regions(struct damon_ctx *ctx); +void kdamond_prepare_vm_access_checks(struct damon_ctx *ctx); +unsigned int kdamond_check_vm_accesses(struct damon_ctx *ctx); +bool kdamond_vm_target_valid(struct damon_target *t); +void kdamond_vm_cleanup(struct damon_ctx *ctx); + int damon_set_targets(struct damon_ctx *ctx, unsigned long *ids, ssize_t nr_ids); int damon_set_attrs(struct damon_ctx *ctx, unsigned long sample_int, diff --git a/mm/Kconfig b/mm/Kconfig index 8b1dacc60a8e..21cbd394bc78 100644 --- a/mm/Kconfig +++ b/mm/Kconfig @@ -882,6 +882,9 @@ config MAPPING_DIRTY_HELPERS config DAMON bool "Data Access Monitor" + depends on MMU && !IDLE_PAGE_TRACKING + select PAGE_EXTENSION if !64BIT + select PAGE_IDLE_FLAG help This feature allows to monitor access frequency of each memory region. The information can be useful for performance-centric DRAM diff --git a/mm/damon.c b/mm/damon.c index 59d0b59858ae..cec151d60755 100644 --- a/mm/damon.c +++ b/mm/damon.c @@ -9,6 +9,10 @@ * This file is constructed in below parts. * * - Functions and macros for DAMON data structures + * - Functions for the initial monitoring target regions construction + * - Functions for the dynamic monitoring target regions update + * - Functions for the access checking of the regions + * - Functions for the target validity check and cleanup * - Functions for DAMON core logics and features * - Functions for the DAMON programming interface * - Functions for the initialization @@ -20,6 +24,7 @@ #include #include #include +#include #include #include #include @@ -196,6 +201,553 @@ static unsigned long damon_region_sz_limit(struct damon_ctx *ctx) return sz; } +/* + * Functions for the initial monitoring target regions construction + */ + +/* + * 't->id' should be the pointer to the relevant 'struct pid' having reference + * count. Caller must put the returned task, unless it is NULL. + */ +#define damon_get_task_struct(t) \ + (get_pid_task((struct pid *)t->id, PIDTYPE_PID)) + +/* + * Get the mm_struct of the given target + * + * Caller _must_ put the mm_struct after use, unless it is NULL. + * + * Returns the mm_struct of the target on success, NULL on failure + */ +static struct mm_struct *damon_get_mm(struct damon_target *t) +{ + struct task_struct *task; + struct mm_struct *mm; + + task = damon_get_task_struct(t); + if (!task) + return NULL; + + mm = get_task_mm(task); + put_task_struct(task); + return mm; +} + +/* + * Size-evenly split a region into 'nr_pieces' small regions + * + * Returns 0 on success, or negative error code otherwise. + */ +static int damon_split_region_evenly(struct damon_ctx *ctx, + struct damon_region *r, unsigned int nr_pieces) +{ + unsigned long sz_orig, sz_piece, orig_end; + struct damon_region *n = NULL, *next; + unsigned long start; + + if (!r || !nr_pieces) + return -EINVAL; + + orig_end = r->ar.end; + sz_orig = r->ar.end - r->ar.start; + sz_piece = ALIGN_DOWN(sz_orig / nr_pieces, MIN_REGION); + + if (!sz_piece) + return -EINVAL; + + r->ar.end = r->ar.start + sz_piece; + next = damon_next_region(r); + for (start = r->ar.end; start + sz_piece <= orig_end; + start += sz_piece) { + n = damon_new_region(start, start + sz_piece); + if (!n) + return -ENOMEM; + damon_insert_region(n, r, next); + r = n; + } + /* complement last region for possible rounding error */ + if (n) + n->ar.end = orig_end; + + return 0; +} + +static unsigned long sz_range(struct damon_addr_range *r) +{ + return r->end - r->start; +} + +static void swap_ranges(struct damon_addr_range *r1, + struct damon_addr_range *r2) +{ + struct damon_addr_range tmp; + + tmp = *r1; + *r1 = *r2; + *r2 = tmp; +} + +/* + * Find three regions separated by two biggest unmapped regions + * + * vma the head vma of the target address space + * regions an array of three address ranges that results will be saved + * + * This function receives an address space and finds three regions in it which + * separated by the two biggest unmapped regions in the space. Please refer to + * below comments of 'damon_init_vm_regions_of()' function to know why this is + * necessary. + * + * Returns 0 if success, or negative error code otherwise. + */ +static int damon_three_regions_in_vmas(struct vm_area_struct *vma, + struct damon_addr_range regions[3]) +{ + struct damon_addr_range gap = {0}, first_gap = {0}, second_gap = {0}; + struct vm_area_struct *last_vma = NULL; + unsigned long start = 0; + struct rb_root rbroot; + + /* Find two biggest gaps so that first_gap > second_gap > others */ + for (; vma; vma = vma->vm_next) { + if (!last_vma) { + start = vma->vm_start; + goto next; + } + + if (vma->rb_subtree_gap <= sz_range(&second_gap)) { + rbroot.rb_node = &vma->vm_rb; + vma = rb_entry(rb_last(&rbroot), + struct vm_area_struct, vm_rb); + goto next; + } + + gap.start = last_vma->vm_end; + gap.end = vma->vm_start; + if (sz_range(&gap) > sz_range(&second_gap)) { + swap_ranges(&gap, &second_gap); + if (sz_range(&second_gap) > sz_range(&first_gap)) + swap_ranges(&second_gap, &first_gap); + } +next: + last_vma = vma; + } + + if (!sz_range(&second_gap) || !sz_range(&first_gap)) + return -EINVAL; + + /* Sort the two biggest gaps by address */ + if (first_gap.start > second_gap.start) + swap_ranges(&first_gap, &second_gap); + + /* Store the result */ + regions[0].start = ALIGN(start, MIN_REGION); + regions[0].end = ALIGN(first_gap.start, MIN_REGION); + regions[1].start = ALIGN(first_gap.end, MIN_REGION); + regions[1].end = ALIGN(second_gap.start, MIN_REGION); + regions[2].start = ALIGN(second_gap.end, MIN_REGION); + regions[2].end = ALIGN(last_vma->vm_end, MIN_REGION); + + return 0; +} + +/* + * Get the three regions in the given target (task) + * + * Returns 0 on success, negative error code otherwise. + */ +static int damon_three_regions_of(struct damon_target *t, + struct damon_addr_range regions[3]) +{ + struct mm_struct *mm; + int rc; + + mm = damon_get_mm(t); + if (!mm) + return -EINVAL; + + mmap_read_lock(mm); + rc = damon_three_regions_in_vmas(mm->mmap, regions); + mmap_read_unlock(mm); + + mmput(mm); + return rc; +} + +/* + * Initialize the monitoring target regions for the given target (task) + * + * t the given target + * + * Because only a number of small portions of the entire address space + * is actually mapped to the memory and accessed, monitoring the unmapped + * regions is wasteful. That said, because we can deal with small noises, + * tracking every mapping is not strictly required but could even incur a high + * overhead if the mapping frequently changes or the number of mappings is + * high. The adaptive regions adjustment mechanism will further help to deal + * with the noise by simply identifying the unmapped areas as a region that + * has no access. Moreover, applying the real mappings that would have many + * unmapped areas inside will make the adaptive mechanism quite complex. That + * said, too huge unmapped areas inside the monitoring target should be removed + * to not take the time for the adaptive mechanism. + * + * For the reason, we convert the complex mappings to three distinct regions + * that cover every mapped area of the address space. Also the two gaps + * between the three regions are the two biggest unmapped areas in the given + * address space. In detail, this function first identifies the start and the + * end of the mappings and the two biggest unmapped areas of the address space. + * Then, it constructs the three regions as below: + * + * [mappings[0]->start, big_two_unmapped_areas[0]->start) + * [big_two_unmapped_areas[0]->end, big_two_unmapped_areas[1]->start) + * [big_two_unmapped_areas[1]->end, mappings[nr_mappings - 1]->end) + * + * As usual memory map of processes is as below, the gap between the heap and + * the uppermost mmap()-ed region, and the gap between the lowermost mmap()-ed + * region and the stack will be two biggest unmapped regions. Because these + * gaps are exceptionally huge areas in usual address space, excluding these + * two biggest unmapped regions will be sufficient to make a trade-off. + * + * + * + * + * (other mmap()-ed regions and small unmapped regions) + * + * + * + */ +static void damon_init_vm_regions_of(struct damon_ctx *c, + struct damon_target *t) +{ + struct damon_region *r; + struct damon_addr_range regions[3]; + unsigned long sz = 0, nr_pieces; + int i; + + if (damon_three_regions_of(t, regions)) { + pr_err("Failed to get three regions of target %lu\n", t->id); + return; + } + + for (i = 0; i < 3; i++) + sz += regions[i].end - regions[i].start; + if (c->min_nr_regions) + sz /= c->min_nr_regions; + if (sz < MIN_REGION) + sz = MIN_REGION; + + /* Set the initial three regions of the target */ + for (i = 0; i < 3; i++) { + r = damon_new_region(regions[i].start, regions[i].end); + if (!r) { + pr_err("%d'th init region creation failed\n", i); + return; + } + damon_add_region(r, t); + + nr_pieces = (regions[i].end - regions[i].start) / sz; + damon_split_region_evenly(c, r, nr_pieces); + } +} + +/* Initialize '->regions_list' of every target (task) */ +void kdamond_init_vm_regions(struct damon_ctx *ctx) +{ + struct damon_target *t; + + damon_for_each_target(t, ctx) { + /* the user may set the target regions as they want */ + if (!nr_damon_regions(t)) + damon_init_vm_regions_of(ctx, t); + } +} + +/* + * Functions for the dynamic monitoring target regions update + */ + +/* + * Check whether a region is intersecting an address range + * + * Returns true if it is. + */ +static bool damon_intersect(struct damon_region *r, struct damon_addr_range *re) +{ + return !(r->ar.end <= re->start || re->end <= r->ar.start); +} + +/* + * Update damon regions for the three big regions of the given target + * + * t the given target + * bregions the three big regions of the target + */ +static void damon_apply_three_regions(struct damon_ctx *ctx, + struct damon_target *t, struct damon_addr_range bregions[3]) +{ + struct damon_region *r, *next; + unsigned int i = 0; + + /* Remove regions which are not in the three big regions now */ + damon_for_each_region_safe(r, next, t) { + for (i = 0; i < 3; i++) { + if (damon_intersect(r, &bregions[i])) + break; + } + if (i == 3) + damon_destroy_region(r); + } + + /* Adjust intersecting regions to fit with the three big regions */ + for (i = 0; i < 3; i++) { + struct damon_region *first = NULL, *last; + struct damon_region *newr; + struct damon_addr_range *br; + + br = &bregions[i]; + /* Get the first and last regions which intersects with br */ + damon_for_each_region(r, t) { + if (damon_intersect(r, br)) { + if (!first) + first = r; + last = r; + } + if (r->ar.start >= br->end) + break; + } + if (!first) { + /* no damon_region intersects with this big region */ + newr = damon_new_region( + ALIGN_DOWN(br->start, MIN_REGION), + ALIGN(br->end, MIN_REGION)); + if (!newr) + continue; + damon_insert_region(newr, damon_prev_region(r), r); + } else { + first->ar.start = ALIGN_DOWN(br->start, MIN_REGION); + last->ar.end = ALIGN(br->end, MIN_REGION); + } + } +} + +/* + * Update regions for current memory mappings + */ +void kdamond_update_vm_regions(struct damon_ctx *ctx) +{ + struct damon_addr_range three_regions[3]; + struct damon_target *t; + + damon_for_each_target(t, ctx) { + if (damon_three_regions_of(t, three_regions)) + continue; + damon_apply_three_regions(ctx, t, three_regions); + } +} + +/* + * Functions for the access checking of the regions + */ + +static void damon_ptep_mkold(pte_t *pte, struct mm_struct *mm, + unsigned long addr) +{ + bool referenced = false; + struct page *page = pte_page(*pte); + + if (pte_young(*pte)) { + referenced = true; + *pte = pte_mkold(*pte); + } + +#ifdef CONFIG_MMU_NOTIFIER + if (mmu_notifier_clear_young(mm, addr, addr + PAGE_SIZE)) + referenced = true; +#endif /* CONFIG_MMU_NOTIFIER */ + + if (referenced) + set_page_young(page); + + set_page_idle(page); +} + +static void damon_pmdp_mkold(pmd_t *pmd, struct mm_struct *mm, + unsigned long addr) +{ +#ifdef CONFIG_TRANSPARENT_HUGEPAGE + bool referenced = false; + struct page *page = pmd_page(*pmd); + + if (pmd_young(*pmd)) { + referenced = true; + *pmd = pmd_mkold(*pmd); + } + +#ifdef CONFIG_MMU_NOTIFIER + if (mmu_notifier_clear_young(mm, addr, + addr + ((1UL) << HPAGE_PMD_SHIFT))) + referenced = true; +#endif /* CONFIG_MMU_NOTIFIER */ + + if (referenced) + set_page_young(page); + + set_page_idle(page); +#endif /* CONFIG_TRANSPARENT_HUGEPAGE */ +} + +static void damon_mkold(struct mm_struct *mm, unsigned long addr) +{ + pte_t *pte = NULL; + pmd_t *pmd = NULL; + spinlock_t *ptl; + + if (follow_pte_pmd(mm, addr, NULL, &pte, &pmd, &ptl)) + return; + + if (pte) { + damon_ptep_mkold(pte, mm, addr); + pte_unmap_unlock(pte, ptl); + } else { + damon_pmdp_mkold(pmd, mm, addr); + spin_unlock(ptl); + } +} + +static void damon_prepare_vm_access_check(struct damon_ctx *ctx, + struct mm_struct *mm, struct damon_region *r) +{ + r->sampling_addr = damon_rand(r->ar.start, r->ar.end); + + damon_mkold(mm, r->sampling_addr); +} + +void kdamond_prepare_vm_access_checks(struct damon_ctx *ctx) +{ + struct damon_target *t; + struct mm_struct *mm; + struct damon_region *r; + + damon_for_each_target(t, ctx) { + mm = damon_get_mm(t); + if (!mm) + continue; + damon_for_each_region(r, t) + damon_prepare_vm_access_check(ctx, mm, r); + mmput(mm); + } +} + +static bool damon_young(struct mm_struct *mm, unsigned long addr, + unsigned long *page_sz) +{ + pte_t *pte = NULL; + pmd_t *pmd = NULL; + spinlock_t *ptl; + bool young = false; + + if (follow_pte_pmd(mm, addr, NULL, &pte, &pmd, &ptl)) + return false; + + *page_sz = PAGE_SIZE; + if (pte) { + young = pte_young(*pte); + if (!young) + young = !page_is_idle(pte_page(*pte)); + pte_unmap_unlock(pte, ptl); + return young; + } + +#ifdef CONFIG_TRANSPARENT_HUGEPAGE + young = pmd_young(*pmd); + if (!young) + young = !page_is_idle(pmd_page(*pmd)); + spin_unlock(ptl); + *page_sz = ((1UL) << HPAGE_PMD_SHIFT); +#endif /* CONFIG_TRANSPARENT_HUGEPAGE */ + + return young; +} + +/* + * Check whether the region was accessed after the last preparation + * + * mm 'mm_struct' for the given virtual address space + * r the region to be checked + */ +static void damon_check_vm_access(struct damon_ctx *ctx, + struct mm_struct *mm, struct damon_region *r) +{ + static struct mm_struct *last_mm; + static unsigned long last_addr; + static unsigned long last_page_sz = PAGE_SIZE; + static bool last_accessed; + + /* If the region is in the last checked page, reuse the result */ + if (mm == last_mm && (ALIGN_DOWN(last_addr, last_page_sz) == + ALIGN_DOWN(r->sampling_addr, last_page_sz))) { + if (last_accessed) + r->nr_accesses++; + return; + } + + last_accessed = damon_young(mm, r->sampling_addr, &last_page_sz); + if (last_accessed) + r->nr_accesses++; + + last_mm = mm; + last_addr = r->sampling_addr; +} + +unsigned int kdamond_check_vm_accesses(struct damon_ctx *ctx) +{ + struct damon_target *t; + struct mm_struct *mm; + struct damon_region *r; + unsigned int max_nr_accesses = 0; + + damon_for_each_target(t, ctx) { + mm = damon_get_mm(t); + if (!mm) + continue; + damon_for_each_region(r, t) { + damon_check_vm_access(ctx, mm, r); + max_nr_accesses = max(r->nr_accesses, max_nr_accesses); + } + mmput(mm); + } + + return max_nr_accesses; +} + + +/* + * Functions for the target validity check and cleanup + */ + +bool kdamond_vm_target_valid(struct damon_target *t) +{ + struct task_struct *task; + + task = damon_get_task_struct(t); + if (task) { + put_task_struct(task); + return true; + } + + return false; +} + +void kdamond_vm_cleanup(struct damon_ctx *ctx) +{ + struct damon_target *t, *next; + + damon_for_each_target_safe(t, next, ctx) { + put_pid((struct pid *)t->id); + damon_destroy_target(t); + } +} + /* * Functions for DAMON core logics and features */ From patchwork Mon Aug 17 10:51:29 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: SeongJae Park X-Patchwork-Id: 11717997 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 6868613A4 for ; Mon, 17 Aug 2020 10:55:09 +0000 (UTC) Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by mail.kernel.org (Postfix) with ESMTP id 2796320758 for ; Mon, 17 Aug 2020 10:55:09 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (1024-bit key) header.d=amazon.com header.i=@amazon.com header.b="NGTENIgd" DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org 2796320758 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 5A73D6B0006; Mon, 17 Aug 2020 06:55:08 -0400 (EDT) Delivered-To: linux-mm-outgoing@kvack.org Received: by kanga.kvack.org (Postfix, from userid 40) id 555A46B000C; Mon, 17 Aug 2020 06:55:08 -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 41E3D6B000D; Mon, 17 Aug 2020 06:55:08 -0400 (EDT) X-Original-To: linux-mm@kvack.org X-Delivered-To: linux-mm@kvack.org Received: from forelay.hostedemail.com (smtprelay0230.hostedemail.com [216.40.44.230]) by kanga.kvack.org (Postfix) with ESMTP id 2A70F6B0006 for ; Mon, 17 Aug 2020 06:55:08 -0400 (EDT) Received: from smtpin05.hostedemail.com (10.5.19.251.rfc1918.com [10.5.19.251]) by forelay04.hostedemail.com (Postfix) with ESMTP id E25672495 for ; Mon, 17 Aug 2020 10:55:07 +0000 (UTC) X-FDA: 77159753454.05.list71_431573227016 Received: from filter.hostedemail.com (10.5.16.251.rfc1918.com [10.5.16.251]) by smtpin05.hostedemail.com (Postfix) with ESMTP id B6880180199BC for ; Mon, 17 Aug 2020 10:55:07 +0000 (UTC) X-Spam-Summary: 1,0,0,,d41d8cd98f00b204,prvs=491cff689=sjpark@amazon.com,,RULES_HIT:30003:30012:30034:30051:30054:30064:30070:30075:30080,0,RBL:72.21.198.25:@amazon.com:.lbl8.mailshell.net-62.18.0.100 66.10.201.10;04y8hnyccbwc48czampw9a451y9bbocc3a75uiqktxmtd9fmpw1q5r8xotjpf19.7kzb6dan4kekswishtsrbnefhr1bjbgiebkp913nhiq4et5jfxjgq8or5qrmr5p.k-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:108,LUA_SUMMARY:none X-HE-Tag: list71_431573227016 X-Filterd-Recvd-Size: 11190 Received: from smtp-fw-4101.amazon.com (smtp-fw-4101.amazon.com [72.21.198.25]) by imf08.hostedemail.com (Postfix) with ESMTP for ; Mon, 17 Aug 2020 10:55:06 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=amazon.com; i=@amazon.com; q=dns/txt; s=amazon201209; t=1597661707; x=1629197707; h=from:to:cc:subject:date:message-id:in-reply-to: references:mime-version; bh=k6WU8X8uUioiTj7c3Ke/KLWkbXXGCVDmB5Ldj54XnIY=; b=NGTENIgdquIQBTZlcgbLwhGXyKSa7UPBLvT2xVd42HZRWmj0SHtkMCQg a4JvkW6hNS7EnkibW4fbyREhY2OVz7laCSqDsm5MnphWpjLoa+5RoAJuR otefM4a9kgJKOr/ZLYRdYoQZgdJPv59MxI/lfB6zshJiYt7qcvmeVMxvt U=; X-IronPort-AV: E=Sophos;i="5.76,322,1592870400"; d="scan'208";a="48282142" Received: from iad12-co-svc-p1-lb1-vlan3.amazon.com (HELO email-inbound-relay-1d-2c665b5d.us-east-1.amazon.com) ([10.43.8.6]) by smtp-border-fw-out-4101.iad4.amazon.com with ESMTP; 17 Aug 2020 10:55:06 +0000 Received: from EX13MTAUEA002.ant.amazon.com (iad55-ws-svc-p15-lb9-vlan2.iad.amazon.com [10.40.159.162]) by email-inbound-relay-1d-2c665b5d.us-east-1.amazon.com (Postfix) with ESMTPS id C9FDAA1BCE; Mon, 17 Aug 2020 10:54:54 +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; Mon, 17 Aug 2020 10:54:53 +0000 Received: from u3f2cd687b01c55.ant.amazon.com (10.43.160.192) by EX13D31EUA001.ant.amazon.com (10.43.165.15) with Microsoft SMTP Server (TLS) id 15.0.1497.2; Mon, 17 Aug 2020 10:54:37 +0000 From: SeongJae Park To: CC: SeongJae Park , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , Subject: [PATCH v20 07/15] mm/damon: Implement access pattern recording Date: Mon, 17 Aug 2020 12:51:29 +0200 Message-ID: <20200817105137.19296-8-sjpark@amazon.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20200817105137.19296-1-sjpark@amazon.com> References: <20200817105137.19296-1-sjpark@amazon.com> MIME-Version: 1.0 X-Originating-IP: [10.43.160.192] X-ClientProxiedBy: EX13D02UWC004.ant.amazon.com (10.43.162.236) To EX13D31EUA001.ant.amazon.com (10.43.165.15) X-Rspamd-Queue-Id: B6880180199BC X-Spamd-Result: default: False [0.00 / 100.00] X-Rspamd-Server: rspam02 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 This commit implements the recording feature of DAMON. If this feature is enabled, DAMON writes the monitored access patterns in its binary format into a file which specified by the user. This is already able to be implemented by each user using the callbacks. However, as the recording is expected to be widely used, this commit implements the feature in the DAMON, for more convenience. Signed-off-by: SeongJae Park Reviewed-by: Leonard Foerster --- include/linux/damon.h | 15 +++++ mm/damon.c | 142 +++++++++++++++++++++++++++++++++++++++++- 2 files changed, 154 insertions(+), 3 deletions(-) diff --git a/include/linux/damon.h b/include/linux/damon.h index 945eb9259acf..54cdc1366f59 100644 --- a/include/linux/damon.h +++ b/include/linux/damon.h @@ -75,6 +75,14 @@ struct damon_target { * in case of virtual memory monitoring) and applies the changes for each * @regions_update_interval. All time intervals are in micro-seconds. * + * @rbuf: In-memory buffer for monitoring result recording. + * @rbuf_len: The length of @rbuf. + * @rbuf_offset: The offset for next write to @rbuf. + * @rfile_path: Record file path. + * + * If @rbuf, @rbuf_len, and @rfile_path are set, the monitored results are + * automatically stored in @rfile_path file. + * * @kdamond: Kernel thread who does the monitoring. * @kdamond_stop: Notifies whether kdamond should stop. * @kdamond_lock: Mutex for the synchronizations with @kdamond. @@ -142,6 +150,11 @@ struct damon_ctx { struct timespec64 last_aggregation; struct timespec64 last_regions_update; + unsigned char *rbuf; + unsigned int rbuf_len; + unsigned int rbuf_offset; + char *rfile_path; + struct task_struct *kdamond; bool kdamond_stop; struct mutex kdamond_lock; @@ -172,6 +185,8 @@ int damon_set_targets(struct damon_ctx *ctx, int damon_set_attrs(struct damon_ctx *ctx, unsigned long sample_int, unsigned long aggr_int, unsigned long regions_update_int, unsigned long min_nr_reg, unsigned long max_nr_reg); +int damon_set_recording(struct damon_ctx *ctx, + unsigned int rbuf_len, char *rfile_path); int damon_start(struct damon_ctx *ctxs, int nr_ctxs); int damon_stop(struct damon_ctx *ctxs, int nr_ctxs); diff --git a/mm/damon.c b/mm/damon.c index cec151d60755..fed35f7b3879 100644 --- a/mm/damon.c +++ b/mm/damon.c @@ -57,6 +57,10 @@ #define damon_for_each_target_safe(t, next, ctx) \ list_for_each_entry_safe(t, next, &(ctx)->targets_list, list) +#define MIN_RECORD_BUFFER_LEN 1024 +#define MAX_RECORD_BUFFER_LEN (4 * 1024 * 1024) +#define MAX_RFILE_PATH_LEN 256 + /* Get a random number in [l, r) */ #define damon_rand(l, r) (l + prandom_u32() % (r - l)) @@ -785,16 +789,89 @@ static bool kdamond_aggregate_interval_passed(struct damon_ctx *ctx) } /* - * Reset the aggregated monitoring results + * Flush the content in the result buffer to the result file + */ +static void damon_flush_rbuffer(struct damon_ctx *ctx) +{ + ssize_t sz; + loff_t pos = 0; + struct file *rfile; + + if (!ctx->rbuf_offset) + return; + + rfile = filp_open(ctx->rfile_path, + O_CREAT | O_RDWR | O_APPEND | O_LARGEFILE, 0644); + if (IS_ERR(rfile)) { + pr_err("Cannot open the result file %s\n", + ctx->rfile_path); + return; + } + + while (ctx->rbuf_offset) { + sz = kernel_write(rfile, ctx->rbuf, ctx->rbuf_offset, &pos); + if (sz < 0) + break; + ctx->rbuf_offset -= sz; + } + filp_close(rfile, NULL); +} + +/* + * Write a data into the result buffer + */ +static void damon_write_rbuf(struct damon_ctx *ctx, void *data, ssize_t size) +{ + if (!ctx->rbuf_len || !ctx->rbuf || !ctx->rfile_path) + return; + if (ctx->rbuf_offset + size > ctx->rbuf_len) + damon_flush_rbuffer(ctx); + if (ctx->rbuf_offset + size > ctx->rbuf_len) { + pr_warn("%s: flush failed, or wrong size given(%u, %zu)\n", + __func__, ctx->rbuf_offset, size); + return; + } + + memcpy(&ctx->rbuf[ctx->rbuf_offset], data, size); + ctx->rbuf_offset += size; +} + +/* + * Flush the aggregated monitoring results to the result buffer + * + * Stores current tracking results to the result buffer and reset 'nr_accesses' + * of each region. The format for the result buffer is as below: + * + *