Re: [PATCH v23 02/15] mm/damon/core: Implement region-based sampling
On Mon, 1 Feb 2021 09:37:29 -0800 Shakeel Butt wrote:
> On Tue, Dec 15, 2020 at 3:56 AM SeongJae Park wrote:
> >
> > From: SeongJae Park
> >
> > To avoid the unbounded increase of the overhead, DAMON groups adjacent
> > pages that assumed to have the same access frequencies into a region.
>
> 'that are assumed'
Good eye!
>
> > 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``,
> >
> > 1. the 'prepare_access_checks' primitive picks one page in each region,
> > 2. waits for one ``sampling interval``,
> > 3. checks whether the page is accessed meanwhile, and
> > 4. increases the access frequency of the region if so.
>
> I think you meant increasing the access 'count' or something.
> Increasing the access frequency somewhat conveys that the sampling
> interval is being decreased.
You're right, I will reword this in the next version.
>
> >
> > Therefore, the monitoring overhead is controllable by adjusting the
> > number of regions. DAMON allows both the underlying primitives and user
> > callbacks adjust regions for the trade-off. In other words, this commit
>
> 'callbacks to adjust'
Nice catch!
>
>
> > makes DAMON to use not only time-based sampling but also space-based
> > sampling.
> >
> > This scheme, however, cannot preserve the quality of the output if the
> > assumption is not guaranteed. Next commit will address this problem.
> >
> > Another problem of this region abstraction is additional memory space
> > overhead for the regions metadata. For example, suppose page
> > granularity monitoring that doesn't want to know fine-grained access
> > frequency but only if each page accessed or not.
>
> You mean when the sampling interval is equal to the aggregation interval,
> right?
Right, that would be a straightforward way to get the information with region
abstraction.
>
> > Then, we can do that
> > by directly resetting and reading the PG_Idle flags and/or the PTE
> > Accessed bits. The metadata for the region abstraction is only burden
> > in the case. For the reason, this commit makes DAMON to support the
> > user-defined arbitrary target, which could be stored in a void pointer
> > of the monitoring context with specific target type.
>
> Sorry I didn't follow. How does sampling interval equal to aggregation
> interval require user-defined arbitrary targets?
So, setting sampling interval equal to aggregation interval is a
straightforward way to get the if-accessed-only information with the
region-based sampling. However, this will waste memory with region metadata
(observed accesses counter). The wastage becomes much worse if we do
page-granularity monitoring, because the region metadata for start address and
end address of the regions would not necessary.
Someone can implement and use monitoring primitives making no such waste by
using thir own abstraction rather than the regions abstraction (and therefore
no regions metadata). To allow that, we make the regions abstraction to be
used only when the context is configured for special target type
(DAMON_REGION_SAMPLING_TARGET) and allow users to use their own arbitrary
abstraction with the arbitrary target type.
An RFC patchset for an example implementation of the arbitrary target type is
available:
https://lore.kernel.org/linux-mm/20201216094221.11898-1-sjp...@amazon.com/
>
> >
> > Signed-off-by: SeongJae Park
> > Reviewed-by: Leonard Foerster
> > ---
> > include/linux/damon.h | 109 ++--
> > mm/damon/core.c | 142 +-
> > 2 files changed, 243 insertions(+), 8 deletions(-)
> >
> > diff --git a/include/linux/damon.h b/include/linux/damon.h
> > index 387fa4399fc8..7d4685adc8a9 100644
> > --- a/include/linux/damon.h
> > +++ b/include/linux/damon.h
> > @@ -12,6 +12,48 @@
> > #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.
> > +
Re: [PATCH v23 02/15] mm/damon/core: Implement region-based sampling
On Tue, Dec 15, 2020 at 3:56 AM SeongJae Park wrote:
>
> From: SeongJae Park
>
> To avoid the unbounded increase of the overhead, DAMON groups adjacent
> pages that assumed to have the same access frequencies into a region.
'that are assumed'
> 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``,
>
> 1. the 'prepare_access_checks' primitive picks one page in each region,
> 2. waits for one ``sampling interval``,
> 3. checks whether the page is accessed meanwhile, and
> 4. increases the access frequency of the region if so.
I think you meant increasing the access 'count' or something.
Increasing the access frequency somewhat conveys that the sampling
interval is being decreased.
>
> Therefore, the monitoring overhead is controllable by adjusting the
> number of regions. DAMON allows both the underlying primitives and user
> callbacks adjust regions for the trade-off. In other words, this commit
'callbacks to adjust'
> makes DAMON to use not only time-based sampling but also space-based
> sampling.
>
> This scheme, however, cannot preserve the quality of the output if the
> assumption is not guaranteed. Next commit will address this problem.
>
> Another problem of this region abstraction is additional memory space
> overhead for the regions metadata. For example, suppose page
> granularity monitoring that doesn't want to know fine-grained access
> frequency but only if each page accessed or not.
You mean when the sampling interval is equal to the aggregation interval, right?
> Then, we can do that
> by directly resetting and reading the PG_Idle flags and/or the PTE
> Accessed bits. The metadata for the region abstraction is only burden
> in the case. For the reason, this commit makes DAMON to support the
> user-defined arbitrary target, which could be stored in a void pointer
> of the monitoring context with specific target type.
Sorry I didn't follow. How does sampling interval equal to aggregation
interval require user-defined arbitrary targets?
>
> Signed-off-by: SeongJae Park
> Reviewed-by: Leonard Foerster
> ---
> include/linux/damon.h | 109 ++--
> mm/damon/core.c | 142 +-
> 2 files changed, 243 insertions(+), 8 deletions(-)
>
> diff --git a/include/linux/damon.h b/include/linux/damon.h
> index 387fa4399fc8..7d4685adc8a9 100644
> --- a/include/linux/damon.h
> +++ b/include/linux/damon.h
> @@ -12,6 +12,48 @@
> #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;
>
> /**
> @@ -36,7 +78,8 @@ struct damon_ctx;
> *
> * @init_target_regions should construct proper monitoring target regions and
> * link those to the DAMON context struct. The regions should be defined by
> - * user and saved in @damon_ctx.target.
> + * user and saved in @damon_ctx.arbitrary_target if @damon_ctx.target_type is
> + * _ARBITRARY_TARGET. Otherwise, damon_region should be used.
> * @update_target_regions should update the monitoring target regions for
> * current status.
> * @prepare_access_checks should manipulate the monitoring regions to be
> @@ -46,7 +89,8 @@ struct damon_ctx;
> * @reset_aggregated should reset the access monitoring results that
> aggregated
> * by @check_accesses.
> * @target_valid should
