| Message ID | 20201020085940.13875-2-sjpark@amazon.com (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
| Series | Introduce Data Access MONitor (DAMON) | expand |
On Tue, Oct 20, 2020 at 2:01 AM SeongJae Park <sjpark@amazon.com> wrote: > > From: SeongJae Park <sjpark@amazon.de> > > DAMON is a data access monitoring framework for the Linux kernel. The > core mechanisms of DAMON make it > > - accurate (the monitoring output is useful enough for DRAM level > performance-centric memory management; It might be inappropriate for > CPU Cache levels, though), > - light-weight (the monitoring overhead is normally 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, hence, we can easily write efficient kernel space > data access monitoring applications. For example, the kernel's memory > management mechanisms can make advanced decisions using this. > Experimental data access aware optimization works that incurring high > access monitoring overhead could implemented again on top of this. > > Due to its simple and flexible interface, providing user space interface > would be also easy. Then, user space users who have some special > workloads can write personalized applications for better understanding > and optimizations of their workloads and systems. > > That said, this commit is implementing only 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 <sjpark@amazon.de> > Reviewed-by: Leonard Foerster <foersleo@amazon.de> > Reviewed-by: Varad Gautam <vrd@amazon.de> I don't see any benefit of this patch on its own. Some of this should be part of the main damon context patch. I would suggest to separate the core (damon context) from the target related structs (target, region, addr range). Also I would prefer the code be added with the actual usage otherwise it is hard to review. > --- [snip] > +unsigned int damon_nr_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; > +} Why not keep a count instead of traversing to get the size?
Hi Shakeel, Thanks for the review! :D On Wed, 25 Nov 2020 07:29:10 -0800 Shakeel Butt <shakeelb@google.com> wrote: > On Tue, Oct 20, 2020 at 2:01 AM SeongJae Park <sjpark@amazon.com> wrote: > > > > From: SeongJae Park <sjpark@amazon.de> > > > > DAMON is a data access monitoring framework for the Linux kernel. The > > core mechanisms of DAMON make it > > > > - accurate (the monitoring output is useful enough for DRAM level > > performance-centric memory management; It might be inappropriate for > > CPU Cache levels, though), > > - light-weight (the monitoring overhead is normally 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, hence, we can easily write efficient kernel space > > data access monitoring applications. For example, the kernel's memory > > management mechanisms can make advanced decisions using this. > > Experimental data access aware optimization works that incurring high > > access monitoring overhead could implemented again on top of this. > > > > Due to its simple and flexible interface, providing user space interface > > would be also easy. Then, user space users who have some special > > workloads can write personalized applications for better understanding > > and optimizations of their workloads and systems. > > > > That said, this commit is implementing only 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 <sjpark@amazon.de> > > Reviewed-by: Leonard Foerster <foersleo@amazon.de> > > Reviewed-by: Varad Gautam <vrd@amazon.de> > > I don't see any benefit of this patch on its own. Some of this should > be part of the main damon context patch. Agreed. Will change so in the next version. > I would suggest to separate > the core (damon context) from the target related structs (target, > region, addr range). To be honest, I unsure if I'm fully understanding what specific change you want to make. So if I'm misunderstanding your point below, please let me know. Seems like you are concerning for future support of special kind use cases that don't need targets/regions/addresses, such as page granularity monitoring that having interest in only if the pages accessed or not, rather than access frequency. In the context, your suggestion makes sense as the region abstraction is only burden in the case, as I also mentioned in the cover letter. This could be done via idle pages tracking, but DAMON will be able to do this faster by reducing the number of user-kernel context switches. I once considered adding some change in the core part for efficient support of such use cases, but resulted in believing that the best way for that is implementing another primitive for the case and use it in a controlled way. In a high level, it should disable the 'adaptive regions adjustment' feature and define it's own targets structs other than the damon_target. Then, your implementation of the primitive callbacks should use your own targets. In more detail, the 'adaptive regions adjustment' can be disabled by setting the min_nr_regions and max_nr_regions of the damon_ctx with same value, say, 0. Your own targets structs could be stored in 'damon_callback->private'. Or, we could add another 'private' field in damon_ctx for that. I think this will work, but I also admit that this could look like a hairy hack to someone. Fundamentally, this is because the region based overhead/accuracy handling is strongly coupled in the design. So, I think what you are really suggesting is making DAMON more general by default and supporting the region based overhead/accuracy handling additionally. If I'm understanding correctly, how about below like change? Obviously this should be cleaned up a lot, but I just want to quickly share my idea and discuss. Also note that it's based on the damon/next tree[1]. [1] https://github.com/sjp38/linux/tree/damon/next +enum damon_type { + ARBITRARY_TARGETS, + ADAPTIVE_REGIONS, +}; + +struct damon_adaptive_regions_ctx { + unsigned long min_nr_regions; + unsigned long max_nr_regions; + struct list_head targets; + struct list_head schemes; +}; + /** * 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 @@ -243,8 +255,6 @@ 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; @@ -253,11 +263,14 @@ struct damon_ctx { bool kdamond_stop; struct mutex kdamond_lock; - struct list_head targets_list; /* 'damon_target' objects */ - struct list_head schemes_list; /* 'damos' objects */ - struct damon_primitive primitive; struct damon_callback callback; + + enum damon_type type; + union { + struct damon_adaptive_regions_ctx arctx; + void *targets; + }; }; The patchset will first introduce DAMON as only ARBITRARY_TARGETS (or, would TINY be a better name?) type supporting form. After that, following patch will add ADAPTIVE_REGIONS type support. Do you think I'm correctly understanding your point and above suggestion makes sense? > > Also I would prefer the code be added with the actual usage otherwise > it is hard to review. Agreed. Will do so in the next version. > > > --- > [snip] > > +unsigned int damon_nr_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; > > +} > > Why not keep a count instead of traversing to get the size? First of all, because this makes code simpler while this is not confirmed as bottleneck, yet. Because users can set the max_nr_regions, I think this will not be real problem in the region based overhead/accuracy handling case. In case of the 'ARBITRARY_TARGETS', this will not used at all. I also prefer this because the user could add/remove regions on their own inside their callbacks. Thanks, SeongJae Park
On Thu, 26 Nov 2020 12:51:57 +0100 SeongJae Park <sjpark@amazon.com> wrote: > Hi Shakeel, > > > Thanks for the review! :D > > On Wed, 25 Nov 2020 07:29:10 -0800 Shakeel Butt <shakeelb@google.com> wrote: > > > On Tue, Oct 20, 2020 at 2:01 AM SeongJae Park <sjpark@amazon.com> wrote: > > > > > > From: SeongJae Park <sjpark@amazon.de> > > > > > > DAMON is a data access monitoring framework for the Linux kernel. The > > > core mechanisms of DAMON make it > > > > > > - accurate (the monitoring output is useful enough for DRAM level > > > performance-centric memory management; It might be inappropriate for > > > CPU Cache levels, though), > > > - light-weight (the monitoring overhead is normally 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, hence, we can easily write efficient kernel space > > > data access monitoring applications. For example, the kernel's memory > > > management mechanisms can make advanced decisions using this. > > > Experimental data access aware optimization works that incurring high > > > access monitoring overhead could implemented again on top of this. > > > > > > Due to its simple and flexible interface, providing user space interface > > > would be also easy. Then, user space users who have some special > > > workloads can write personalized applications for better understanding > > > and optimizations of their workloads and systems. > > > > > > That said, this commit is implementing only 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 <sjpark@amazon.de> > > > Reviewed-by: Leonard Foerster <foersleo@amazon.de> > > > Reviewed-by: Varad Gautam <vrd@amazon.de> > > [...] > > I would suggest to separate > > the core (damon context) from the target related structs (target, > > region, addr range). > > To be honest, I unsure if I'm fully understanding what specific change you want > to make. So if I'm misunderstanding your point below, please let me know. > > Seems like you are concerning for future support of special kind use cases that > don't need targets/regions/addresses, such as page granularity monitoring that > having interest in only if the pages accessed or not, rather than access > frequency. In the context, your suggestion makes sense as the region > abstraction is only burden in the case, as I also mentioned in the cover > letter. This could be done via idle pages tracking, but DAMON will be able to > do this faster by reducing the number of user-kernel context switches. > > I once considered adding some change in the core part for efficient support of > such use cases, but resulted in believing that the best way for that is > implementing another primitive for the case and use it in a controlled way. > > In a high level, it should disable the 'adaptive regions adjustment' feature > and define it's own targets structs other than the damon_target. Then, your > implementation of the primitive callbacks should use your own targets. > > In more detail, the 'adaptive regions adjustment' can be disabled by setting > the min_nr_regions and max_nr_regions of the damon_ctx with same value, say, 0. > Your own targets structs could be stored in 'damon_callback->private'. Or, we > could add another 'private' field in damon_ctx for that. > > I think this will work, but I also admit that this could look like a hairy > hack to someone. Fundamentally, this is because the region based > overhead/accuracy handling is strongly coupled in the design. So, I think what > you are really suggesting is making DAMON more general by default and > supporting the region based overhead/accuracy handling additionally. > > If I'm understanding correctly, how about below like change? Obviously this > should be cleaned up a lot, but I just want to quickly share my idea and > discuss. Also note that it's based on the damon/next tree[1]. > > [1] https://github.com/sjp38/linux/tree/damon/next > > +enum damon_type { > + ARBITRARY_TARGETS, > + ADAPTIVE_REGIONS, > +}; > + > +struct damon_adaptive_regions_ctx { > + unsigned long min_nr_regions; > + unsigned long max_nr_regions; > + struct list_head targets; > + struct list_head schemes; > +}; > + > /** > * 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 > @@ -243,8 +255,6 @@ 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; > @@ -253,11 +263,14 @@ struct damon_ctx { > bool kdamond_stop; > struct mutex kdamond_lock; > > - struct list_head targets_list; /* 'damon_target' objects */ > - struct list_head schemes_list; /* 'damos' objects */ > - > struct damon_primitive primitive; > struct damon_callback callback; > + > + enum damon_type type; > + union { > + struct damon_adaptive_regions_ctx arctx; > + void *targets; > + }; > }; > > The patchset will first introduce DAMON as only ARBITRARY_TARGETS (or, would > TINY be a better name?) type supporting form. After that, following patch will > add ADAPTIVE_REGIONS type support. Do you think I'm correctly understanding > your point and above suggestion makes sense? In a private message, Shakeel confirmed I'm correnctly understanding his intention and asked next version. I will post next version soon. Thanks, SeongJae Park
diff --git a/include/linux/damon.h b/include/linux/damon.h new file mode 100644 index 000000000000..183e0edd7f43 --- /dev/null +++ b/include/linux/damon.h @@ -0,0 +1,95 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +/* + * DAMON api + * + * Author: SeongJae Park <sjpark@amazon.de> + */ + +#ifndef _DAMON_H_ +#define _DAMON_H_ + +#include <linux/types.h> + +/** + * 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. + * @nr_accesses: Access frequency of this region. + * @list: List head for siblings. + */ +struct damon_region { + struct damon_addr_range ar; + 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 */ +}; + +#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) + +#ifdef CONFIG_DAMON + +struct damon_region *damon_new_region(unsigned long start, unsigned long end); +inline void damon_insert_region(struct damon_region *r, + struct damon_region *prev, struct damon_region *next); +void damon_add_region(struct damon_region *r, struct damon_target *t); +void damon_destroy_region(struct damon_region *r); + +struct damon_target *damon_new_target(unsigned long id); +void damon_add_target(struct damon_ctx *ctx, struct damon_target *t); +void damon_free_target(struct damon_target *t); +void damon_destroy_target(struct damon_target *t); +unsigned int damon_nr_regions(struct damon_target *t); + +#endif /* CONFIG_DAMON */ + +#endif diff --git a/mm/Kconfig b/mm/Kconfig index 6c974888f86f..19fe2251c87a 100644 --- a/mm/Kconfig +++ b/mm/Kconfig @@ -868,4 +868,6 @@ config ARCH_HAS_HUGEPD config MAPPING_DIRTY_HELPERS bool +source "mm/damon/Kconfig" + endmenu diff --git a/mm/Makefile b/mm/Makefile index d5649f1c12c0..5d969d09521b 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/ diff --git a/mm/damon/Kconfig b/mm/damon/Kconfig new file mode 100644 index 000000000000..d00e99ac1a15 --- /dev/null +++ b/mm/damon/Kconfig @@ -0,0 +1,15 @@ +# SPDX-License-Identifier: GPL-2.0-only + +menu "Data Access Monitoring" + +config DAMON + bool "DAMON: Data Access Monitoring Framework" + help + This builds a framework that allows kernel subsystems 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. + +endmenu diff --git a/mm/damon/Makefile b/mm/damon/Makefile new file mode 100644 index 000000000000..4fd2edb4becf --- /dev/null +++ b/mm/damon/Makefile @@ -0,0 +1,3 @@ +# SPDX-License-Identifier: GPL-2.0 + +obj-$(CONFIG_DAMON) := core.o diff --git a/mm/damon/core.c b/mm/damon/core.c new file mode 100644 index 000000000000..4562b2458719 --- /dev/null +++ b/mm/damon/core.c @@ -0,0 +1,121 @@ +// SPDX-License-Identifier: GPL-2.0 +/* + * Data Access Monitor + * + * Author: SeongJae Park <sjpark@amazon.de> + */ + +#define pr_fmt(fmt) "damon: " fmt + +#include <linux/damon.h> +#include <linux/slab.h> + +/* + * Functions and macros for DAMON data structures + */ + +/* + * Construct a damon_region struct + * + * Returns the pointer to the new struct if success, or NULL otherwise + */ +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 + */ +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); +} + +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); +} + +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 + */ +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; +} + +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); +} + +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); +} + +void damon_destroy_target(struct damon_target *t) +{ + damon_del_target(t); + damon_free_target(t); +} + +unsigned int damon_nr_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; +}