lkml.org 
[lkml]   [2023]   [Nov]   [20]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
Patch in this message
/
Date
SubjectRe: [PATCH v2 1/4] mm/ksm: add ksm advisor
From
On 28.10.23 02:09, Stefan Roesch wrote:
> This adds the ksm advisor. The ksm advisor automatically manages the
> pages_to_scan setting to achieve a target scan time. The target scan
> time defines how many seconds it should take to scan all the candidate
> KSM pages. In other words the pages_to_scan rate is changed by the
> advisor to achieve the target scan time. The algorithm has a max and min
> value to:
> - guarantee responsiveness to changes
> - to avoid to spend too much CPU
>
> The respective parameters are:
> - ksm_advisor_target_scan_time (how many seconds a scan should take)
> - ksm_advisor_min_cpu (minimum value for cpu percent usage)
> - ksm_advisor_max_cpu (maximum value for cpu percent usage)
>
> - ksm_advisor_min_pages (minimum value for pages_to_scan per batch)
> - ksm_advisor_max_pages (maximum value for pages_to_scan per batch)
>
> The algorithm calculates the change value based on the target scan time
> and the previous scan time. To avoid pertubations an exponentially
> weighted moving average is applied.
>
> The advisor is managed by three main parameters: target scan time,
> cpu min time and cpu max time for the ksmd background thread. These
> parameters determine how aggresive ksmd scans.
>
> In addition there are min and max values for the pages_to_scan parameter
> to make sure that its initial and max values are not set too low or too
> high. This ensures that it is able to react to changes quickly enough.
>
> The default values are:
> - target scan time: 200 secs
> - min cpu: 15%
> - max cpu: 70%
> - min pages: 500
> - max pages: 30000

Do we really need the min cpu load? The target scan time combined with
the max CPU load should be sufficient, no?

Internally, we might want some sane default/min start value, but
exposing that to the user is questionable.

For example, if I have exactly two possible KSM pages in the system, why
should my cpu dedicate 15% to scanning nothing after merging them? :)

[...]

> +/**
> + * struct advisor_ctx - metadata for KSM advisor
> + * @start_scan: start time of the current scan
> + * @scan_time: scan time of previous scan
> + * @change: change in percent to pages_to_scan parameter
> + * @cpu_percent: average cpu percent usage of the ksmd thread for the last scan
> + */
> +struct advisor_ctx {
> + ktime_t start_scan;
> + unsigned long scan_time;
> + unsigned long change;
> + unsigned long long cpu_time;
> +};
> +static struct advisor_ctx advisor_ctx;
> +
> +/* Define different advisor's */
> +enum ksm_advisor_type {
> + KSM_ADVISOR_NONE,
> + KSM_ADVISOR_FIRST = KSM_ADVISOR_NONE,

Unused, better drop it. 0 is the implicit first one.

> + KSM_ADVISOR_SCAN_TIME,
> + KSM_ADVISOR_LAST = KSM_ADVISOR_SCAN_TIME

Instead of "_LAST", maybe use "_COUNT" and use that when checking for
valid values.

But: we likely want to store "strings" instead of magic numbers from
user space instead.

> +};
> +static enum ksm_advisor_type ksm_advisor;
> +
> +static void init_advisor(void)
> +{
> + advisor_ctx.start_scan = 0;
> + advisor_ctx.scan_time = 0;
> + advisor_ctx.change = 0;
> + advisor_ctx.cpu_time = 0;
> +}

That should likely not be required. The values are all 0.

If other values are ever required, they could be initialized right with
the variable:

static struct advisor_ctx advisor_ctx = {
.start_scan = 0,
...
};

> +
> +/*
> + * Use previous scan time if available, otherwise use current scan time as an
> + * approximation for the previous scan time.
> + */
> +static inline unsigned long prev_scan_time(struct advisor_ctx *ctx,
> + unsigned long scan_time)
> +{
> + return ctx->scan_time ? ctx->scan_time : scan_time;
> +}
> +
> +/* Calculate exponential weighted moving average */
> +static unsigned long ewma(unsigned long prev, unsigned long curr)
> +{
> + return ((100 - EWMA_WEIGHT) * prev + EWMA_WEIGHT * curr) / 100;
> +}
> +
> +/*
> + * The scan time advisor is based on the current scan rate and the target
> + * scan rate.
> + *
> + * new_pages_to_scan = pages_to_scan * (scan_time / target_scan_time)
> + *
> + * To avoid pertubations it calculates a change factor of previous changes.
> + * A new change factor is calculated for each iteration and it uses an
> + * exponentially weighted moving average. The new pages_to_scan value is
> + * multiplied with that change factor:
> + *
> + * new_pages_to_scan *= change facor
> + *
> + * In addition the new pages_to_scan value is capped by the max and min
> + * limits.
> + */
> +static void scan_time_advisor(unsigned long scan_time)
> +{
> + unsigned int cpu_percent;
> + unsigned long cpu_time;
> + unsigned long cpu_time_diff;
> + unsigned long cpu_time_diff_ms;
> + unsigned long pages;
> + unsigned long per_page_cost;
> + unsigned long factor;
> + unsigned long change;
> + unsigned long last_scan_time;
> +
> + cpu_time = task_sched_runtime(current);
> + cpu_time_diff = cpu_time - advisor_ctx.cpu_time;
> + cpu_time_diff_ms = cpu_time_diff / 1000 / 1000;
> +
> + cpu_percent = (cpu_time_diff_ms * 100) / (scan_time * 1000);
> + cpu_percent = cpu_percent ? cpu_percent : 1;
> + last_scan_time = prev_scan_time(&advisor_ctx, scan_time);
> +
> + /* Calculate scan time as percentage of target scan time */
> + factor = ksm_advisor_target_scan_time * 100 / scan_time;
> + factor = factor ? factor : 1;
> +
> + /*
> + * Calculate scan time as percentage of last scan time and use
> + * exponentially weighted average to smooth it
> + */
> + change = scan_time * 100 / last_scan_time;
> + change = change ? change : 1;
> + change = ewma(advisor_ctx.change, change);
> +
> + /* Calculate new scan rate based on target scan rate. */
> + pages = ksm_thread_pages_to_scan * 100 / factor;
> + /* Update pages_to_scan by weighted change percentage. */
> + pages = pages * change / 100;
> +
> + /* Cap new pages_to_scan value */
> + per_page_cost = ksm_thread_pages_to_scan / cpu_percent;
> + per_page_cost = per_page_cost ? per_page_cost : 1;
> +
> + pages = min(pages, per_page_cost * ksm_advisor_max_cpu);
> + pages = max(pages, per_page_cost * ksm_advisor_min_cpu);
> + pages = min(pages, ksm_advisor_max_pages);
> +
> + /* Update advisor context */
> + advisor_ctx.change = change;
> + advisor_ctx.scan_time = scan_time;
> + advisor_ctx.cpu_time = cpu_time;
> +
> + ksm_thread_pages_to_scan = pages;

While that advisor is active, we should likely disallow changing
ksm_thread_pages_to_scan using other means.

> +}
> +
> +static void run_advisor(void)
> +{
> + if (ksm_advisor == KSM_ADVISOR_SCAN_TIME) {
> + s64 scan_time;
> +
> + /* Convert scan time to seconds */
> + scan_time = ktime_ms_delta(ktime_get(), advisor_ctx.start_scan);
> + scan_time = div_s64(scan_time, MSEC_PER_SEC);
> + scan_time = scan_time ? scan_time : 1;
> +
> + scan_time_advisor((unsigned long)scan_time);
> + }

We could have rescheduled in the meantime, right? Doesn't that mean that
our CPU load consumption might be wrong in some cases?

> +}
> +
> #ifdef CONFIG_NUMA
> /* Zeroed when merging across nodes is not allowed */
> static unsigned int ksm_merge_across_nodes = 1;
> @@ -2401,6 +2554,7 @@ static struct ksm_rmap_item *scan_get_next_rmap_item(struct page **page)
>
> mm_slot = ksm_scan.mm_slot;
> if (mm_slot == &ksm_mm_head) {
> + advisor_ctx.start_scan = ktime_get();

Why do that even without KSM_ADVISOR_SCAN_TIME?

You should probably have two functions:

ksm_advisor_start_scan() [this code, fenced by KSM_ADVISOR_SCAN_TIME]
ksm_advisor_stop_scan() [previous run_advisor]

> trace_ksm_start_scan(ksm_scan.seqnr, ksm_rmap_items);
>
> /*
> @@ -2558,6 +2712,8 @@ static struct ksm_rmap_item *scan_get_next_rmap_item(struct page **page)
> if (mm_slot != &ksm_mm_head)
> goto next_mm;
>
> + run_advisor();
> +
> trace_ksm_stop_scan(ksm_scan.seqnr, ksm_rmap_items);
> ksm_scan.seqnr++;
> return NULL;
> @@ -3603,6 +3759,7 @@ static int __init ksm_init(void)
> zero_checksum = calc_checksum(ZERO_PAGE(0));
> /* Default to false for backwards compatibility */
> ksm_use_zero_pages = false;
> + init_advisor();
>
> err = ksm_slab_init();
> if (err)

--
Cheers,

David / dhildenb

\
 
 \ /
  Last update: 2023-11-20 14:05    [W:1.349 / U:0.008 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site