#define pr_fmt(fmt) "damon: " fmt
#include <linux/damon.h>
#include <linux/delay.h>
#include <linux/kthread.h>
#include <linux/memcontrol.h>
#include <linux/mm.h>
#include <linux/pid.h>
#include <linux/psi.h>
#include <linux/sched.h>
#include <linux/slab.h>
#include <linux/string.h>
#include "ops-common.h"
#define CREATE_TRACE_POINTS
#include <trace/events/damon.h>
static DEFINE_MUTEX(damon_lock);
static int nr_running_ctxs;
static bool running_exclusive_ctxs;
static DEFINE_MUTEX(damon_ops_lock);
static struct damon_operations damon_registered_ops[NR_DAMON_OPS];
static struct kmem_cache *damon_region_cache __ro_after_init;
static bool __damon_is_registered_ops(enum damon_ops_id id)
{
struct damon_operations empty_ops = {};
if (!memcmp(&empty_ops, &damon_registered_ops[id], sizeof(empty_ops)))
return false;
return true;
}
bool damon_is_registered_ops(enum damon_ops_id id)
{
bool registered;
if (id >= NR_DAMON_OPS)
return false;
mutex_lock(&damon_ops_lock);
registered = __damon_is_registered_ops(id);
mutex_unlock(&damon_ops_lock);
return registered;
}
int damon_register_ops(struct damon_operations *ops)
{
int err = 0;
if (ops->id >= NR_DAMON_OPS)
return -EINVAL;
mutex_lock(&damon_ops_lock);
if (__damon_is_registered_ops(ops->id))
err = -EINVAL;
else
damon_registered_ops[ops->id] = *ops;
mutex_unlock(&damon_ops_lock);
return err;
}
int damon_select_ops(struct damon_ctx *ctx, enum damon_ops_id id)
{
int err = 0;
if (id >= NR_DAMON_OPS)
return -EINVAL;
mutex_lock(&damon_ops_lock);
if (!__damon_is_registered_ops(id))
err = -EINVAL;
else
ctx->ops = damon_registered_ops[id];
mutex_unlock(&damon_ops_lock);
return err;
}
struct damon_prep *damon_new_prep(enum damon_prep_action action)
{
struct damon_prep *prep;
prep = kmalloc_obj(*prep);
if (!prep)
return NULL;
prep->action = action;
INIT_LIST_HEAD(&prep->list);
return prep;
}
void damon_add_prep(struct damon_probe *p, struct damon_prep *prep)
{
list_add_tail(&prep->list, &p->preps);
}
static void damon_del_prep(struct damon_prep *p)
{
list_del(&p->list);
}
static void damon_free_prep(struct damon_prep *p)
{
kfree(p);
}
static void damon_destroy_prep(struct damon_prep *p)
{
damon_del_prep(p);
damon_free_prep(p);
}
static struct damon_prep *damon_nth_prep(int n, struct damon_probe *p)
{
struct damon_prep *prep;
int i = 0;
damon_for_each_prep(prep, p) {
if (i++ == n)
return prep;
}
return NULL;
}
static bool damon_has_prep(struct damon_ctx *c)
{
struct damon_prep *prep;
struct damon_probe *probe;
damon_for_each_probe(probe, c) {
damon_for_each_prep(prep, probe)
return true;
}
return false;
}
struct damon_filter *damon_new_filter(enum damon_filter_type type,
bool matching, bool allow)
{
struct damon_filter *filter;
filter = kmalloc_obj(*filter);
if (!filter)
return NULL;
filter->type = type;
filter->matching = matching;
filter->allow = allow;
INIT_LIST_HEAD(&filter->list);
return filter;
}
void damon_add_filter(struct damon_probe *p, struct damon_filter *f)
{
list_add_tail(&f->list, &p->filters);
}
static void damon_del_filter(struct damon_filter *f)
{
list_del(&f->list);
}
static void damon_free_filter(struct damon_filter *f)
{
kfree(f);
}
void damon_destroy_filter(struct damon_filter *f)
{
damon_del_filter(f);
damon_free_filter(f);
}
static struct damon_filter *damon_nth_filter(int n, struct damon_probe *p)
{
struct damon_filter *f;
int i = 0;
damon_for_each_filter(f, p) {
if (i++ == n)
return f;
}
return NULL;
}
struct damon_probe *damon_new_probe(void)
{
struct damon_probe *p;
p = kmalloc_obj(*p);
if (!p)
return NULL;
p->weight = 0;
INIT_LIST_HEAD(&p->preps);
INIT_LIST_HEAD(&p->filters);
INIT_LIST_HEAD(&p->list);
return p;
}
void damon_add_probe(struct damon_ctx *ctx, struct damon_probe *probe)
{
list_add_tail(&probe->list, &ctx->probes);
}
static void damon_del_probe(struct damon_probe *p)
{
list_del(&p->list);
}
static void damon_free_probe(struct damon_probe *p)
{
struct damon_prep *prep, *prep_next;
struct damon_filter *f, *next;
damon_for_each_prep_safe(prep, prep_next, p)
damon_free_prep(prep);
damon_for_each_filter_safe(f, next, p)
damon_free_filter(f);
kfree(p);
}
static void damon_destroy_probe(struct damon_probe *p)
{
damon_del_probe(p);
damon_free_probe(p);
}
static struct damon_probe *damon_nth_probe(int n, struct damon_ctx *ctx)
{
struct damon_probe *p;
int i = 0;
damon_for_each_probe(p, ctx) {
if (i++ == n)
return p;
}
return NULL;
}
static bool damon_has_probe_weights(struct damon_ctx *c)
{
struct damon_probe *p;
damon_for_each_probe(p, c) {
if (p->weight)
return true;
}
return false;
}
static unsigned long damon_mvsum(unsigned long current_nr,
unsigned long last_nr, unsigned long left_window_bp)
{
return current_nr + mult_frac(last_nr, left_window_bp, 10000);
}
unsigned int damon_nr_accesses_mvsum(struct damon_region *r,
struct damon_ctx *ctx)
{
unsigned long sample_interval, aggr_interval;
unsigned long window_len, left_window, left_window_bp;
sample_interval = ctx->attrs.sample_interval ? : 1;
aggr_interval = ctx->attrs.aggr_interval ? : 1;
window_len = aggr_interval / sample_interval;
if (time_after_eq(ctx->passed_sample_intervals,
ctx->next_aggregation_sis))
left_window = 0;
else
left_window = ctx->next_aggregation_sis -
ctx->passed_sample_intervals;
left_window_bp = mult_frac(left_window, 10000, window_len);
if (left_window_bp == 10000)
return r->last_nr_accesses;
return damon_mvsum(r->nr_accesses, r->last_nr_accesses,
left_window_bp);
}
unsigned char damon_probe_hits_mvsum(int probe_idx, struct damon_region *r,
struct damon_ctx *ctx)
{
unsigned long sample_interval, aggr_interval;
unsigned long window_len, left_window, left_window_bp;
sample_interval = ctx->attrs.sample_interval ? : 1;
aggr_interval = ctx->attrs.aggr_interval ? : 1;
window_len = aggr_interval / sample_interval;
if (time_after_eq(ctx->passed_sample_intervals,
ctx->next_aggregation_sis))
left_window = 0;
else
left_window = ctx->next_aggregation_sis -
ctx->passed_sample_intervals;
left_window_bp = mult_frac(left_window, 10000, window_len);
if (left_window_bp == 10000)
return r->last_probe_hits[probe_idx];
return damon_mvsum(r->probe_hits[probe_idx],
r->last_probe_hits[probe_idx], left_window_bp);
}
#ifdef CONFIG_DAMON_DEBUG_SANITY
static void damon_verify_new_region(unsigned long start, unsigned long end)
{
WARN_ONCE(start >= end, "start %lu >= end %lu\n", start, end);
}
#else
static void damon_verify_new_region(unsigned long start, unsigned long end)
{
}
#endif
struct damon_region *damon_new_region(unsigned long start, unsigned long end)
{
struct damon_region *region;
int i;
damon_verify_new_region(start, end);
region = kmem_cache_alloc(damon_region_cache, GFP_KERNEL);
if (!region)
return NULL;
region->ar.start = start;
region->ar.end = end;
region->nr_accesses = 0;
for (i = 0; i < DAMON_MAX_PROBES; i++) {
region->probe_hits[i] = 0;
region->last_probe_hits[i] = 0;
}
INIT_LIST_HEAD(®ion->list);
region->age = 0;
region->last_nr_accesses = 0;
return region;
}
static void damon_add_region(struct damon_region *r, struct damon_target *t)
{
list_add_tail(&r->list, &t->regions_list);
t->nr_regions++;
}
static inline void damon_insert_region(struct damon_region *r,
struct damon_region *prev, struct damon_region *next,
struct damon_target *t)
{
__list_add(&r->list, &prev->list, &next->list);
t->nr_regions++;
}
#ifdef CONFIG_DAMON_DEBUG_SANITY
static void damon_verify_del_region(struct damon_target *t)
{
WARN_ONCE(t->nr_regions == 0, "t->nr_regions == 0\n");
}
#else
static void damon_verify_del_region(struct damon_target *t)
{
}
#endif
static void damon_del_region(struct damon_region *r, struct damon_target *t)
{
damon_verify_del_region(t);
list_del(&r->list);
t->nr_regions--;
}
static void damon_free_region(struct damon_region *r)
{
kmem_cache_free(damon_region_cache, r);
}
static void damon_destroy_region(struct damon_region *r,
struct damon_target *t)
{
damon_del_region(r, t);
damon_free_region(r);
}
static bool damon_is_last_region(struct damon_region *r,
struct damon_target *t)
{
return list_is_last(&r->list, &t->regions_list);
}
unsigned int damon_probe_hits_wsum(struct damon_region *r, bool last, bool mv,
struct damon_ctx *ctx)
{
struct damon_probe *probe;
unsigned int sum = 0;
int i = 0;
damon_for_each_probe(probe, ctx) {
if (last)
sum += r->last_probe_hits[i++] * probe->weight;
else if (mv)
sum += damon_probe_hits_mvsum(i++, r, ctx) *
probe->weight;
else
sum += r->probe_hits[i++] * probe->weight;
}
return sum;
}
static bool damon_intersect(struct damon_region *r,
struct damon_addr_range *re)
{
return !(r->ar.end <= re->start || re->end <= r->ar.start);
}
static int damon_fill_regions_holes(struct damon_region *first,
struct damon_region *last, struct damon_target *t)
{
struct damon_region *r = first;
damon_for_each_region_from(r, t) {
struct damon_region *next, *newr;
if (r == last)
break;
next = damon_next_region(r);
if (r->ar.end != next->ar.start) {
newr = damon_new_region(r->ar.end, next->ar.start);
if (!newr)
return -ENOMEM;
damon_insert_region(newr, r, next, t);
}
}
return 0;
}
int damon_set_regions(struct damon_target *t, struct damon_addr_range *ranges,
unsigned int nr_ranges, unsigned long min_region_sz)
{
struct damon_region *r, *next;
unsigned int i;
unsigned long last_end;
int err;
for (i = 0; i < nr_ranges; i++) {
unsigned long start, end;
start = ALIGN_DOWN(ranges[i].start, min_region_sz);
end = ALIGN(ranges[i].end, min_region_sz);
if (start >= end)
return -EINVAL;
if (i > 0 && last_end > start)
return -EINVAL;
last_end = end;
}
damon_for_each_region_safe(r, next, t) {
for (i = 0; i < nr_ranges; i++) {
if (damon_intersect(r, &ranges[i]))
break;
}
if (i == nr_ranges)
damon_destroy_region(r, t);
}
if (!damon_nr_regions(t)) {
for (i = 0; i < nr_ranges; i++) {
r = damon_new_region(
ALIGN_DOWN(ranges[i].start,
min_region_sz),
ALIGN(ranges[i].end, min_region_sz));
if (!r)
return -ENOMEM;
damon_add_region(r, t);
}
return 0;
}
r = damon_first_region(t);
for (i = 0; i < nr_ranges; i++) {
struct damon_region *first = NULL, *last, *newr;
struct damon_addr_range *range;
bool insert_before_r = false;
range = &ranges[i];
damon_for_each_region_from(r, t) {
if (damon_intersect(r, range)) {
if (!first)
first = r;
last = r;
}
if (r->ar.start >= range->end) {
insert_before_r = true;
break;
}
}
if (!first) {
newr = damon_new_region(
ALIGN_DOWN(range->start,
min_region_sz),
ALIGN(range->end, min_region_sz));
if (!newr)
return -ENOMEM;
if (insert_before_r)
damon_insert_region(newr, damon_prev_region(r),
r, t);
else
damon_add_region(newr, t);
} else {
first->ar.start = ALIGN_DOWN(range->start,
min_region_sz);
last->ar.end = ALIGN(range->end, min_region_sz);
err = damon_fill_regions_holes(first, last, t);
if (err)
return err;
}
}
return 0;
}
struct damos_filter *damos_new_filter(enum damos_filter_type type,
bool matching, bool allow)
{
struct damos_filter *filter;
filter = kmalloc_obj(*filter);
if (!filter)
return NULL;
filter->type = type;
filter->matching = matching;
filter->allow = allow;
INIT_LIST_HEAD(&filter->list);
return filter;
}
bool damos_filter_for_ops(enum damos_filter_type type)
{
switch (type) {
case DAMOS_FILTER_TYPE_ADDR:
case DAMOS_FILTER_TYPE_TARGET:
case DAMOS_FILTER_TYPE_PROBE_HITS_WSUM:
return false;
default:
break;
}
return true;
}
void damos_add_filter(struct damos *s, struct damos_filter *f)
{
if (damos_filter_for_ops(f->type))
list_add_tail(&f->list, &s->ops_filters);
else
list_add_tail(&f->list, &s->core_filters);
}
static void damos_del_filter(struct damos_filter *f)
{
list_del(&f->list);
}
static void damos_free_filter(struct damos_filter *f)
{
kfree(f);
}
void damos_destroy_filter(struct damos_filter *f)
{
damos_del_filter(f);
damos_free_filter(f);
}
struct damos_quota_goal *damos_new_quota_goal(
enum damos_quota_goal_metric metric, bool complement,
unsigned long target_value)
{
struct damos_quota_goal *goal;
goal = kmalloc_obj(*goal);
if (!goal)
return NULL;
goal->metric = metric;
goal->complement = complement;
goal->target_value = target_value;
if (metric == DAMOS_QUOTA_SOME_MEM_PSI_US)
goal->last_psi_total = U64_MAX;
INIT_LIST_HEAD(&goal->list);
return goal;
}
void damos_add_quota_goal(struct damos_quota *q, struct damos_quota_goal *g)
{
list_add_tail(&g->list, &q->goals);
}
static void damos_del_quota_goal(struct damos_quota_goal *g)
{
list_del(&g->list);
}
static void damos_free_quota_goal(struct damos_quota_goal *g)
{
kfree(g);
}
void damos_destroy_quota_goal(struct damos_quota_goal *g)
{
damos_del_quota_goal(g);
damos_free_quota_goal(g);
}
static bool damos_quota_goals_empty(struct damos_quota *q)
{
return list_empty(&q->goals);
}
static void damos_quota_init(struct damos_quota *quota)
{
quota->esz = 0;
quota->total_charged_sz = 0;
quota->total_charged_ns = 0;
quota->charged_sz = 0;
quota->charged_from = 0;
quota->charge_target_from = NULL;
quota->charge_addr_from = 0;
quota->esz_bp = 0;
}
struct damos *damon_new_scheme(struct damos_access_pattern *pattern,
enum damos_action action,
unsigned long apply_interval_us,
struct damos_quota *quota,
struct damos_watermarks *wmarks,
int target_nid)
{
struct damos *scheme;
scheme = kmalloc_obj(*scheme);
if (!scheme)
return NULL;
scheme->pattern = *pattern;
scheme->action = action;
scheme->apply_interval_us = apply_interval_us;
scheme->next_apply_sis = 0;
scheme->walk_completed = false;
INIT_LIST_HEAD(&scheme->core_filters);
INIT_LIST_HEAD(&scheme->ops_filters);
scheme->stat = (struct damos_stat){};
scheme->max_nr_snapshots = 0;
scheme->last_applied = NULL;
INIT_LIST_HEAD(&scheme->list);
scheme->quota = *quota;
damos_quota_init(&scheme->quota);
INIT_LIST_HEAD(&scheme->quota.goals);
scheme->wmarks = *wmarks;
scheme->wmarks.activated = true;
scheme->migrate_dests = (struct damos_migrate_dests){};
scheme->target_nid = target_nid;
return scheme;
}
static void damos_set_next_apply_sis(struct damos *s, struct damon_ctx *ctx)
{
unsigned long sample_interval = ctx->attrs.sample_interval ?
ctx->attrs.sample_interval : 1;
unsigned long apply_interval = s->apply_interval_us ?
s->apply_interval_us : ctx->attrs.aggr_interval;
s->next_apply_sis = ctx->passed_sample_intervals +
apply_interval / sample_interval;
}
void damon_add_scheme(struct damon_ctx *ctx, struct damos *s)
{
list_add_tail(&s->list, &ctx->schemes);
damos_set_next_apply_sis(s, ctx);
}
static void damon_del_scheme(struct damos *s)
{
list_del(&s->list);
}
static void damon_free_scheme(struct damos *s)
{
kfree(s);
}
void damon_destroy_scheme(struct damos *s)
{
struct damos_quota_goal *g, *g_next;
struct damos_filter *f, *next;
damos_for_each_quota_goal_safe(g, g_next, &s->quota)
damos_destroy_quota_goal(g);
damos_for_each_core_filter_safe(f, next, s)
damos_destroy_filter(f);
damos_for_each_ops_filter_safe(f, next, s)
damos_destroy_filter(f);
kfree(s->migrate_dests.node_id_arr);
kfree(s->migrate_dests.weight_arr);
damon_del_scheme(s);
damon_free_scheme(s);
}
struct damon_target *damon_new_target(void)
{
struct damon_target *t;
t = kmalloc_obj(*t);
if (!t)
return NULL;
t->pid = NULL;
t->nr_regions = 0;
INIT_LIST_HEAD(&t->regions_list);
INIT_LIST_HEAD(&t->list);
t->obsolete = false;
return t;
}
void damon_add_target(struct damon_ctx *ctx, struct damon_target *t)
{
list_add_tail(&t->list, &ctx->adaptive_targets);
}
int damon_set_target_pid(struct damon_target *t, int pid)
{
t->pid = find_get_pid(pid);
if (!t->pid)
return -EINVAL;
return 0;
}
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, struct damon_ctx *ctx)
{
if (ctx && ctx->ops.cleanup_target)
ctx->ops.cleanup_target(t);
damon_del_target(t);
damon_free_target(t);
}
unsigned int damon_nr_regions(struct damon_target *t)
{
return t->nr_regions;
}
struct damon_ctx *damon_new_ctx(void)
{
struct damon_ctx *ctx;
ctx = kzalloc_obj(*ctx);
if (!ctx)
return NULL;
init_completion(&ctx->kdamond_started);
ctx->attrs.sample_interval = 5 * 1000;
ctx->attrs.aggr_interval = 100 * 1000;
ctx->attrs.ops_update_interval = 60 * 1000 * 1000;
ctx->passed_sample_intervals = 0;
ctx->next_aggregation_sis = 0;
ctx->next_ops_update_sis = 0;
mutex_init(&ctx->kdamond_lock);
INIT_LIST_HEAD(&ctx->call_controls);
mutex_init(&ctx->call_controls_lock);
mutex_init(&ctx->walk_control_lock);
ctx->attrs.min_nr_regions = 10;
ctx->attrs.max_nr_regions = 1000;
INIT_LIST_HEAD(&ctx->probes);
ctx->addr_unit = 1;
ctx->min_region_sz = DAMON_MIN_REGION_SZ;
INIT_LIST_HEAD(&ctx->adaptive_targets);
INIT_LIST_HEAD(&ctx->schemes);
ctx->call_controls_obsolete = true;
ctx->walk_control_obsolete = true;
prandom_seed_state(&ctx->rnd_state, get_random_u64());
return ctx;
}
static void damon_destroy_targets(struct damon_ctx *ctx)
{
struct damon_target *t, *next_t;
damon_for_each_target_safe(t, next_t, ctx)
damon_destroy_target(t, ctx);
}
void damon_destroy_ctx(struct damon_ctx *ctx)
{
struct damos *s, *next_s;
struct damon_probe *p, *next_p;
damon_destroy_targets(ctx);
damon_for_each_scheme_safe(s, next_s, ctx)
damon_destroy_scheme(s);
damon_for_each_probe_safe(p, next_p, ctx)
damon_destroy_probe(p);
kfree(ctx);
}
static bool damon_attrs_equals(const struct damon_attrs *attrs1,
const struct damon_attrs *attrs2)
{
const struct damon_intervals_goal *ig1 = &attrs1->intervals_goal;
const struct damon_intervals_goal *ig2 = &attrs2->intervals_goal;
return attrs1->sample_interval == attrs2->sample_interval &&
attrs1->aggr_interval == attrs2->aggr_interval &&
attrs1->ops_update_interval == attrs2->ops_update_interval &&
attrs1->min_nr_regions == attrs2->min_nr_regions &&
attrs1->max_nr_regions == attrs2->max_nr_regions &&
ig1->access_bp == ig2->access_bp &&
ig1->aggrs == ig2->aggrs &&
ig1->min_sample_us == ig2->min_sample_us &&
ig1->max_sample_us == ig2->max_sample_us;
}
static unsigned int damon_age_for_new_attrs(unsigned int age,
struct damon_attrs *old_attrs, struct damon_attrs *new_attrs)
{
return age * old_attrs->aggr_interval / new_attrs->aggr_interval;
}
static unsigned int damon_sample_bp_to_count(
unsigned int bp, struct damon_attrs *attrs)
{
return bp * damon_nr_samples_per_aggr(attrs) / 10000;
}
static unsigned int damon_sample_count_to_bp(
unsigned int count, struct damon_attrs *attrs)
{
return mult_frac(count, 10000, damon_nr_samples_per_aggr(attrs));
}
static unsigned int damon_nr_samples_for_new_attrs(unsigned int nr,
struct damon_attrs *old_attrs, struct damon_attrs *new_attrs)
{
return damon_sample_bp_to_count(
damon_sample_count_to_bp(nr, old_attrs), new_attrs);
}
static void damon_update_probe_hits(struct damon_region *r,
struct damon_attrs *old_attrs, struct damon_attrs *new_attrs,
bool aggregating, struct damon_ctx *ctx)
{
struct damon_probe *p;
int i = 0;
damon_for_each_probe(p, ctx) {
r->last_probe_hits[i] = damon_nr_samples_for_new_attrs(
r->last_probe_hits[i], old_attrs, new_attrs);
if (!aggregating)
r->probe_hits[i] = damon_nr_samples_for_new_attrs(
r->probe_hits[i], old_attrs,
new_attrs);
else
r->probe_hits[i] = 0;
i++;
}
}
static void damon_update_monitoring_result(struct damon_region *r,
struct damon_attrs *old_attrs, struct damon_attrs *new_attrs,
bool aggregating, struct damon_ctx *ctx)
{
damon_update_probe_hits(r, old_attrs, new_attrs, aggregating, ctx);
r->last_nr_accesses = damon_nr_samples_for_new_attrs(
r->last_nr_accesses, old_attrs, new_attrs);
if (!aggregating)
r->nr_accesses = damon_nr_samples_for_new_attrs(
r->nr_accesses, old_attrs, new_attrs);
else
r->nr_accesses = 0;
r->age = damon_age_for_new_attrs(r->age, old_attrs, new_attrs);
}
static void damon_update_monitoring_results(struct damon_ctx *ctx,
struct damon_attrs *new_attrs, bool aggregating)
{
struct damon_attrs *old_attrs = &ctx->attrs;
struct damon_target *t;
struct damon_region *r;
if (!old_attrs->sample_interval || !old_attrs->aggr_interval ||
!new_attrs->sample_interval ||
!new_attrs->aggr_interval)
return;
damon_for_each_target(t, ctx)
damon_for_each_region(r, t)
damon_update_monitoring_result(r, old_attrs, new_attrs,
aggregating, ctx);
}
static bool damon_valid_intervals_goal(struct damon_attrs *attrs)
{
struct damon_intervals_goal *goal = &attrs->intervals_goal;
if (!goal->aggrs)
return true;
if (goal->min_sample_us > goal->max_sample_us)
return false;
if (attrs->sample_interval < goal->min_sample_us ||
goal->max_sample_us < attrs->sample_interval)
return false;
return true;
}
int damon_set_attrs(struct damon_ctx *ctx, struct damon_attrs *attrs)
{
unsigned long sample_interval = attrs->sample_interval ?
attrs->sample_interval : 1;
struct damos *s;
bool aggregating = ctx->passed_sample_intervals <
ctx->next_aggregation_sis;
if (!damon_valid_intervals_goal(attrs))
return -EINVAL;
if (attrs->min_nr_regions < 3)
return -EINVAL;
if (attrs->min_nr_regions > attrs->max_nr_regions)
return -EINVAL;
if (attrs->sample_interval > attrs->aggr_interval)
return -EINVAL;
if (!attrs->aggr_samples)
attrs->aggr_samples = attrs->aggr_interval / sample_interval;
ctx->next_aggregation_sis = ctx->passed_sample_intervals +
attrs->aggr_interval / sample_interval;
ctx->next_ops_update_sis = ctx->passed_sample_intervals +
attrs->ops_update_interval / sample_interval;
damon_update_monitoring_results(ctx, attrs, aggregating);
ctx->attrs = *attrs;
damon_for_each_scheme(s, ctx)
damos_set_next_apply_sis(s, ctx);
return 0;
}
void damon_set_schemes(struct damon_ctx *ctx, struct damos **schemes,
ssize_t nr_schemes)
{
struct damos *s, *next;
ssize_t i;
damon_for_each_scheme_safe(s, next, ctx)
damon_destroy_scheme(s);
for (i = 0; i < nr_schemes; i++)
damon_add_scheme(ctx, schemes[i]);
}
static struct damos_quota_goal *damos_nth_quota_goal(
int n, struct damos_quota *q)
{
struct damos_quota_goal *goal;
int i = 0;
damos_for_each_quota_goal(goal, q) {
if (i++ == n)
return goal;
}
return NULL;
}
static void damos_commit_quota_goal_union(
struct damos_quota_goal *dst, struct damos_quota_goal *src)
{
switch (dst->metric) {
case DAMOS_QUOTA_SOME_MEM_PSI_US:
dst->last_psi_total = U64_MAX;
break;
case DAMOS_QUOTA_NODE_MEM_USED_BP:
case DAMOS_QUOTA_NODE_MEM_FREE_BP:
dst->nid = src->nid;
break;
case DAMOS_QUOTA_NODE_MEMCG_USED_BP:
case DAMOS_QUOTA_NODE_MEMCG_FREE_BP:
dst->nid = src->nid;
dst->memcg_id = src->memcg_id;
break;
case DAMOS_QUOTA_NODE_ELIGIBLE_MEM_BP:
dst->nid = src->nid;
break;
default:
break;
}
}
static int damos_commit_quota_goal(
struct damos_quota_goal *dst, struct damos_quota_goal *src)
{
if (!src->target_value)
return -EINVAL;
dst->metric = src->metric;
dst->complement = src->complement;
dst->target_value = src->target_value;
if (dst->metric == DAMOS_QUOTA_USER_INPUT)
dst->current_value = src->current_value;
damos_commit_quota_goal_union(dst, src);
return 0;
}
int damos_commit_quota_goals(struct damos_quota *dst, struct damos_quota *src)
{
struct damos_quota_goal *dst_goal, *next, *src_goal, *new_goal;
int i = 0, j = 0, err;
damos_for_each_quota_goal_safe(dst_goal, next, dst) {
src_goal = damos_nth_quota_goal(i++, src);
if (src_goal) {
err = damos_commit_quota_goal(dst_goal, src_goal);
if (err)
return err;
} else {
damos_destroy_quota_goal(dst_goal);
}
}
damos_for_each_quota_goal_safe(src_goal, next, src) {
if (j++ < i)
continue;
new_goal = damos_new_quota_goal(src_goal->metric,
src_goal->complement, src_goal->target_value);
if (!new_goal)
return -ENOMEM;
err = damos_commit_quota_goal(new_goal, src_goal);
if (err) {
damos_free_quota_goal(new_goal);
return err;
}
damos_add_quota_goal(dst, new_goal);
}
return 0;
}
static int damos_commit_quota(struct damos_quota *dst, struct damos_quota *src)
{
int err;
dst->reset_interval = src->reset_interval;
dst->ms = src->ms;
dst->sz = src->sz;
err = damos_commit_quota_goals(dst, src);
if (err)
return err;
dst->goal_tuner = src->goal_tuner;
dst->fail_charge_num = src->fail_charge_num;
dst->fail_charge_denom = src->fail_charge_denom;
dst->weight_sz = src->weight_sz;
dst->weight_nr_accesses = src->weight_nr_accesses;
dst->weight_age = src->weight_age;
return 0;
}
static struct damos_filter *damos_nth_core_filter(int n, struct damos *s)
{
struct damos_filter *filter;
int i = 0;
damos_for_each_core_filter(filter, s) {
if (i++ == n)
return filter;
}
return NULL;
}
static struct damos_filter *damos_nth_ops_filter(int n, struct damos *s)
{
struct damos_filter *filter;
int i = 0;
damos_for_each_ops_filter(filter, s) {
if (i++ == n)
return filter;
}
return NULL;
}
static int damos_commit_filter_arg(
struct damos_filter *dst, struct damos_filter *src)
{
switch (dst->type) {
case DAMOS_FILTER_TYPE_MEMCG:
dst->memcg_id = src->memcg_id;
break;
case DAMOS_FILTER_TYPE_ADDR:
if (src->addr_range.end < src->addr_range.start)
return -EINVAL;
dst->addr_range = src->addr_range;
break;
case DAMOS_FILTER_TYPE_TARGET:
dst->target_idx = src->target_idx;
break;
case DAMOS_FILTER_TYPE_HUGEPAGE_SIZE:
if (src->sz_range.max < src->sz_range.min)
return -EINVAL;
dst->sz_range = src->sz_range;
break;
case DAMOS_FILTER_TYPE_PROBE_HITS_WSUM:
if (src->range_max < src->range_min)
return -EINVAL;
dst->range_min = src->range_min;
dst->range_max = src->range_max;
break;
default:
break;
}
return 0;
}
static int damos_commit_filter(
struct damos_filter *dst, struct damos_filter *src)
{
dst->type = src->type;
dst->matching = src->matching;
dst->allow = src->allow;
return damos_commit_filter_arg(dst, src);
}
static int damos_commit_core_filters(struct damos *dst, struct damos *src)
{
struct damos_filter *dst_filter, *next, *src_filter, *new_filter;
int i = 0, j = 0, err;
damos_for_each_core_filter_safe(dst_filter, next, dst) {
src_filter = damos_nth_core_filter(i++, src);
if (src_filter) {
err = damos_commit_filter(dst_filter, src_filter);
if (err)
return err;
} else {
damos_destroy_filter(dst_filter);
}
}
damos_for_each_core_filter_safe(src_filter, next, src) {
if (j++ < i)
continue;
new_filter = damos_new_filter(
src_filter->type, src_filter->matching,
src_filter->allow);
if (!new_filter)
return -ENOMEM;
err = damos_commit_filter_arg(new_filter, src_filter);
if (err) {
damos_destroy_filter(new_filter);
return err;
}
damos_add_filter(dst, new_filter);
}
return 0;
}
static int damos_commit_ops_filters(struct damos *dst, struct damos *src)
{
struct damos_filter *dst_filter, *next, *src_filter, *new_filter;
int i = 0, j = 0, err;
damos_for_each_ops_filter_safe(dst_filter, next, dst) {
src_filter = damos_nth_ops_filter(i++, src);
if (src_filter) {
err = damos_commit_filter(dst_filter, src_filter);
if (err)
return err;
} else {
damos_destroy_filter(dst_filter);
}
}
damos_for_each_ops_filter_safe(src_filter, next, src) {
if (j++ < i)
continue;
new_filter = damos_new_filter(
src_filter->type, src_filter->matching,
src_filter->allow);
if (!new_filter)
return -ENOMEM;
err = damos_commit_filter_arg(new_filter, src_filter);
if (err) {
damos_destroy_filter(new_filter);
return err;
}
damos_add_filter(dst, new_filter);
}
return 0;
}
static bool damos_filters_default_reject(struct list_head *filters)
{
struct damos_filter *last_filter;
if (list_empty(filters))
return false;
last_filter = list_last_entry(filters, struct damos_filter, list);
return last_filter->allow;
}
static void damos_set_filters_default_reject(struct damos *s)
{
if (!list_empty(&s->ops_filters))
s->core_filters_default_reject = false;
else
s->core_filters_default_reject =
damos_filters_default_reject(&s->core_filters);
s->ops_filters_default_reject =
damos_filters_default_reject(&s->ops_filters);
}
static bool damon_valid_probe_params(struct damon_ctx *ctx)
{
unsigned long sample_interval;
unsigned char max_probe_hits;
struct damon_probe *probe;
unsigned int wsum, wsum_to_add;
int nr_probes;
nr_probes = 0;
damon_for_each_probe(probe, ctx)
nr_probes++;
if (nr_probes > DAMON_MAX_PROBES)
return false;
if (!damon_has_probe_weights(ctx))
return true;
sample_interval = ctx->attrs.sample_interval ? : 1;
if (ctx->attrs.aggr_interval / sample_interval > U8_MAX)
return false;
max_probe_hits = damon_nr_samples_per_aggr(&ctx->attrs);
wsum = 0;
damon_for_each_probe(probe, ctx) {
if (probe->weight > UINT_MAX / max_probe_hits)
return false;
wsum_to_add = probe->weight * max_probe_hits;
if (UINT_MAX - wsum < wsum_to_add)
return false;
wsum += wsum_to_add;
}
return true;
}
static int damos_commit_dests(struct damos_migrate_dests *dst,
struct damos_migrate_dests *src)
{
if (dst->nr_dests != src->nr_dests) {
kfree(dst->node_id_arr);
kfree(dst->weight_arr);
dst->node_id_arr = kmalloc_objs(*dst->node_id_arr,
src->nr_dests);
if (!dst->node_id_arr) {
dst->weight_arr = NULL;
return -ENOMEM;
}
dst->weight_arr = kmalloc_objs(*dst->weight_arr, src->nr_dests);
if (!dst->weight_arr) {
return -ENOMEM;
}
}
dst->nr_dests = src->nr_dests;
for (int i = 0; i < src->nr_dests; i++) {
dst->node_id_arr[i] = src->node_id_arr[i];
dst->weight_arr[i] = src->weight_arr[i];
}
return 0;
}
static int damos_commit_filters(struct damos *dst, struct damos *src)
{
int err;
err = damos_commit_core_filters(dst, src);
if (err)
return err;
err = damos_commit_ops_filters(dst, src);
if (err)
return err;
damos_set_filters_default_reject(dst);
return 0;
}
static struct damos *damon_nth_scheme(int n, struct damon_ctx *ctx)
{
struct damos *s;
int i = 0;
damon_for_each_scheme(s, ctx) {
if (i++ == n)
return s;
}
return NULL;
}
static int damos_commit(struct damos *dst, struct damos *src)
{
int err;
dst->pattern = src->pattern;
dst->action = src->action;
dst->apply_interval_us = src->apply_interval_us;
err = damos_commit_quota(&dst->quota, &src->quota);
if (err)
return err;
dst->wmarks = src->wmarks;
dst->target_nid = src->target_nid;
err = damos_commit_dests(&dst->migrate_dests, &src->migrate_dests);
if (err)
return err;
err = damos_commit_filters(dst, src);
if (err)
return err;
dst->max_nr_snapshots = src->max_nr_snapshots;
return 0;
}
static int damon_commit_schemes(struct damon_ctx *dst, struct damon_ctx *src)
{
struct damos *dst_scheme, *next, *src_scheme, *new_scheme;
int i = 0, j = 0, err;
damon_for_each_scheme_safe(dst_scheme, next, dst) {
src_scheme = damon_nth_scheme(i++, src);
if (src_scheme) {
err = damos_commit(dst_scheme, src_scheme);
if (err)
return err;
} else {
damon_destroy_scheme(dst_scheme);
}
}
damon_for_each_scheme_safe(src_scheme, next, src) {
if (j++ < i)
continue;
new_scheme = damon_new_scheme(&src_scheme->pattern,
src_scheme->action,
src_scheme->apply_interval_us,
&src_scheme->quota, &src_scheme->wmarks,
NUMA_NO_NODE);
if (!new_scheme)
return -ENOMEM;
err = damos_commit(new_scheme, src_scheme);
if (err) {
damon_destroy_scheme(new_scheme);
return err;
}
damon_add_scheme(dst, new_scheme);
}
return 0;
}
static struct damon_target *damon_nth_target(int n, struct damon_ctx *ctx)
{
struct damon_target *t;
int i = 0;
damon_for_each_target(t, ctx) {
if (i++ == n)
return t;
}
return NULL;
}
static int damon_commit_target_regions(struct damon_target *dst,
struct damon_target *src, unsigned long src_min_region_sz)
{
struct damon_region *src_region, *prev = NULL;
struct damon_addr_range *ranges;
int i = 0, err;
damon_for_each_region(src_region, src) {
if (!prev || prev->ar.end != src_region->ar.start)
i++;
prev = src_region;
}
if (!i)
return 0;
ranges = kvmalloc_objs(*ranges, i, GFP_KERNEL | __GFP_NOWARN);
if (!ranges)
return -ENOMEM;
prev = NULL;
i = 0;
damon_for_each_region(src_region, src) {
if (!prev) {
ranges[i].start = src_region->ar.start;
} else if (prev->ar.end != src_region->ar.start) {
ranges[i++].end = prev->ar.end;
ranges[i].start = src_region->ar.start;
}
prev = src_region;
}
ranges[i++].end = damon_last_region(src)->ar.end;
err = damon_set_regions(dst, ranges, i, src_min_region_sz);
kvfree(ranges);
return err;
}
static int damon_commit_target(
struct damon_target *dst, bool dst_has_pid,
struct damon_target *src, bool src_has_pid,
unsigned long src_min_region_sz)
{
int err;
err = damon_commit_target_regions(dst, src, src_min_region_sz);
if (err)
return err;
if (dst_has_pid)
put_pid(dst->pid);
if (src_has_pid)
get_pid(src->pid);
dst->pid = src->pid;
return 0;
}
static void damon_revert_target_commits(struct damon_ctx *dst,
struct damon_target *failed, struct damon_ctx *src)
{
struct damon_target *target;
if (!damon_target_has_pid(src))
return;
if (dst->ops.cleanup_target)
return;
damon_for_each_target(target, dst) {
if (target == failed)
return;
put_pid(target->pid);
}
}
static int damon_commit_targets(
struct damon_ctx *dst, struct damon_ctx *src)
{
struct damon_target *dst_target, *next, *src_target, *new_target;
struct damon_target *failed;
int i = 0, j = 0, err;
damon_for_each_target_safe(dst_target, next, dst) {
src_target = damon_nth_target(i++, src);
if (src_target && !src_target->obsolete) {
err = damon_commit_target(
dst_target, damon_target_has_pid(dst),
src_target, damon_target_has_pid(src),
src->min_region_sz);
if (err) {
failed = dst_target;
goto out;
}
} else {
struct damos *s;
damon_destroy_target(dst_target, dst);
damon_for_each_scheme(s, dst) {
if (s->quota.charge_target_from == dst_target) {
s->quota.charge_target_from = NULL;
s->quota.charge_addr_from = 0;
}
}
}
}
failed = NULL;
damon_for_each_target_safe(src_target, next, src) {
if (j++ < i)
continue;
if (src_target->obsolete) {
err = -EINVAL;
goto out;
}
new_target = damon_new_target();
if (!new_target) {
err = -ENOMEM;
goto out;
}
err = damon_commit_target(new_target, false,
src_target, damon_target_has_pid(src),
src->min_region_sz);
if (err) {
damon_destroy_target(new_target, NULL);
goto out;
}
damon_add_target(dst, new_target);
}
return 0;
out:
damon_revert_target_commits(dst, failed, src);
return err;
}
static void damon_commit_prep(struct damon_prep *dst, struct damon_prep *src)
{
dst->action = src->action;
}
static int damon_commit_preps(struct damon_probe *dst, struct damon_probe *src)
{
struct damon_prep *dst_prep, *next, *src_prep, *new_prep;
int i = 0, j = 0;
damon_for_each_prep_safe(dst_prep, next, dst) {
src_prep = damon_nth_prep(i++, src);
if (src_prep)
damon_commit_prep(dst_prep, src_prep);
else
damon_destroy_prep(dst_prep);
}
damon_for_each_prep_safe(src_prep, next, src) {
if (j++ < i)
continue;
new_prep = damon_new_prep(src_prep->action);
if (!new_prep)
return -ENOMEM;
damon_add_prep(dst, new_prep);
}
return 0;
}
static int damon_commit_filter(struct damon_filter *dst,
struct damon_filter *src)
{
dst->type = src->type;
dst->matching = src->matching;
dst->allow = src->allow;
switch (dst->type) {
case DAMON_FILTER_TYPE_MEMCG:
dst->memcg_id = src->memcg_id;
break;
case DAMON_FILTER_TYPE_HUGEPAGE_SIZE:
if (src->range_max < src->range_min)
return -EINVAL;
dst->range_min = src->range_min;
dst->range_max = src->range_max;
break;
default:
break;
}
return 0;
}
static int damon_commit_filters(struct damon_probe *dst,
struct damon_probe *src)
{
struct damon_filter *dst_filter, *next, *src_filter, *new_filter;
int i = 0, j = 0, err;
damon_for_each_filter_safe(dst_filter, next, dst) {
src_filter = damon_nth_filter(i++, src);
if (src_filter) {
err = damon_commit_filter(dst_filter, src_filter);
if (err)
return err;
} else {
damon_destroy_filter(dst_filter);
}
}
damon_for_each_filter_safe(src_filter, next, src) {
if (j++ < i)
continue;
new_filter = damon_new_filter(src_filter->type,
src_filter->matching, src_filter->allow);
if (!new_filter)
return -ENOMEM;
switch (src_filter->type) {
case DAMON_FILTER_TYPE_MEMCG:
new_filter->memcg_id = src_filter->memcg_id;
break;
case DAMON_FILTER_TYPE_HUGEPAGE_SIZE:
if (src_filter->range_max < src_filter->range_min) {
damon_destroy_filter(new_filter);
return -EINVAL;
}
new_filter->range_min = src_filter->range_min;
new_filter->range_max = src_filter->range_max;
break;
default:
break;
}
damon_add_filter(dst, new_filter);
}
return 0;
}
static int damon_commit_probes(struct damon_ctx *dst, struct damon_ctx *src)
{
struct damon_probe *dst_probe, *next, *src_probe, *new_probe;
int i = 0, j = 0, err;
damon_for_each_probe_safe(dst_probe, next, dst) {
src_probe = damon_nth_probe(i++, src);
if (src_probe) {
dst_probe->weight = src_probe->weight;
err = damon_commit_preps(dst_probe, src_probe);
if (err)
return err;
err = damon_commit_filters(dst_probe, src_probe);
if (err)
return err;
} else {
damon_destroy_probe(dst_probe);
}
}
damon_for_each_probe_safe(src_probe, next, src) {
if (j++ < i)
continue;
new_probe = damon_new_probe();
if (!new_probe)
return -ENOMEM;
damon_add_probe(dst, new_probe);
new_probe->weight = src_probe->weight;
err = damon_commit_preps(new_probe, src_probe);
if (err)
return err;
err = damon_commit_filters(new_probe, src_probe);
if (err)
return err;
}
return 0;
}
static int __damon_commit_ctx(struct damon_ctx *dst, struct damon_ctx *src)
{
int err;
struct damos *scheme;
struct damos_quota_goal *goal;
dst->maybe_corrupted = true;
if (!is_power_of_2(src->min_region_sz))
return -EINVAL;
if (src->ops.id != DAMON_OPS_PADDR) {
damon_for_each_scheme(scheme, src) {
struct damos_quota *quota = &scheme->quota;
damos_for_each_quota_goal(goal, quota) {
if (goal->metric ==
DAMOS_QUOTA_NODE_ELIGIBLE_MEM_BP)
return -EINVAL;
}
}
}
if (!damon_valid_probe_params(src))
return -EINVAL;
err = damon_commit_schemes(dst, src);
if (err)
return err;
err = damon_commit_targets(dst, src);
if (err)
return err;
if (!damon_attrs_equals(&dst->attrs, &src->attrs)) {
err = damon_set_attrs(dst, &src->attrs);
if (err) {
damon_revert_target_commits(dst, NULL, src);
return err;
}
}
dst->pause = src->pause;
dst->ops = src->ops;
err = damon_commit_probes(dst, src);
if (err)
return err;
dst->addr_unit = src->addr_unit;
dst->min_region_sz = src->min_region_sz;
dst->maybe_corrupted = false;
return 0;
}
static struct damon_ctx *damon_new_test_ctx(struct damon_ctx *dst)
{
struct damon_ctx *test_ctx;
int err;
test_ctx = damon_new_ctx();
if (!test_ctx)
return NULL;
err = __damon_commit_ctx(test_ctx, dst);
if (err) {
damon_destroy_ctx(test_ctx);
return NULL;
}
return test_ctx;
}
int damon_commit_ctx(struct damon_ctx *dst, struct damon_ctx *src)
{
struct damon_ctx *test_ctx;
int err;
test_ctx = damon_new_test_ctx(dst);
if (!test_ctx)
return -ENOMEM;
err = __damon_commit_ctx(test_ctx, src);
if (err)
goto out;
err = __damon_commit_ctx(dst, src);
out:
damon_destroy_ctx(test_ctx);
return err;
}
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 += damon_sz_region(r);
}
if (ctx->attrs.min_nr_regions)
sz /= ctx->attrs.min_nr_regions;
if (sz < ctx->min_region_sz)
sz = ctx->min_region_sz;
return sz;
}
static int damon_split_region_at(struct damon_target *t,
struct damon_region *r, unsigned long sz_r);
static unsigned long damon_apply_min_nr_regions(struct damon_ctx *ctx)
{
unsigned long max_region_sz = damon_region_sz_limit(ctx);
struct damon_target *t;
struct damon_region *r, *next;
max_region_sz = ALIGN(max_region_sz, ctx->min_region_sz);
damon_for_each_target(t, ctx) {
damon_for_each_region_safe(r, next, t) {
while (damon_sz_region(r) > max_region_sz) {
if (damon_split_region_at(t, r, max_region_sz))
goto out;
r = damon_next_region(r);
}
}
}
out:
return max_region_sz;
}
static int kdamond_fn(void *data);
static int __damon_start(struct damon_ctx *ctx)
{
int err = -EBUSY;
mutex_lock(&ctx->kdamond_lock);
if (!ctx->kdamond) {
err = 0;
reinit_completion(&ctx->kdamond_started);
ctx->kdamond = kthread_run(kdamond_fn, ctx, "kdamond.%d",
nr_running_ctxs);
if (IS_ERR(ctx->kdamond)) {
err = PTR_ERR(ctx->kdamond);
ctx->kdamond = NULL;
} else {
wait_for_completion(&ctx->kdamond_started);
}
}
mutex_unlock(&ctx->kdamond_lock);
return err;
}
int damon_start(struct damon_ctx **ctxs, int nr_ctxs, bool exclusive)
{
int i;
int err = 0;
for (i = 0; i < nr_ctxs; i++) {
struct damon_ctx *test_ctx;
test_ctx = damon_new_ctx();
if (!test_ctx)
return -ENOMEM;
err = __damon_commit_ctx(test_ctx, ctxs[i]);
damon_destroy_ctx(test_ctx);
if (err)
return err;
}
mutex_lock(&damon_lock);
if ((exclusive && nr_running_ctxs) ||
(!exclusive && running_exclusive_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++;
}
if (exclusive && nr_running_ctxs)
running_exclusive_ctxs = true;
mutex_unlock(&damon_lock);
if (i != nr_ctxs)
damon_stop(ctxs, i);
return err;
}
static void __damon_stop(struct damon_ctx *ctx)
{
struct task_struct *tsk;
mutex_lock(&ctx->kdamond_lock);
tsk = ctx->kdamond;
if (tsk) {
get_task_struct(tsk);
mutex_unlock(&ctx->kdamond_lock);
kthread_stop_put(tsk);
return;
}
mutex_unlock(&ctx->kdamond_lock);
}
void damon_stop(struct damon_ctx **ctxs, int nr_ctxs)
{
int i;
for (i = 0; i < nr_ctxs; i++)
__damon_stop(ctxs[i]);
}
bool damon_is_running(struct damon_ctx *ctx)
{
bool running;
mutex_lock(&ctx->kdamond_lock);
running = ctx->kdamond != NULL;
mutex_unlock(&ctx->kdamond_lock);
return running;
}
int damon_kdamond_pid(struct damon_ctx *ctx)
{
int pid = -EINVAL;
mutex_lock(&ctx->kdamond_lock);
if (ctx->kdamond)
pid = ctx->kdamond->pid;
mutex_unlock(&ctx->kdamond_lock);
return pid;
}
int damon_call(struct damon_ctx *ctx, struct damon_call_control *control)
{
if (!ctx)
return -EINVAL;
if (!control->repeat)
init_completion(&control->completion);
control->canceled = false;
INIT_LIST_HEAD(&control->list);
mutex_lock(&ctx->call_controls_lock);
if (ctx->call_controls_obsolete) {
mutex_unlock(&ctx->call_controls_lock);
goto canceled;
}
list_add_tail(&control->list, &ctx->call_controls);
mutex_unlock(&ctx->call_controls_lock);
if (control->repeat)
return 0;
wait_for_completion(&control->completion);
if (control->canceled)
goto canceled;
return 0;
canceled:
while (damon_is_running(ctx))
schedule_timeout_idle(msecs_to_jiffies(100));
return -ECANCELED;
}
int damos_walk(struct damon_ctx *ctx, struct damos_walk_control *control)
{
init_completion(&control->completion);
control->canceled = false;
mutex_lock(&ctx->walk_control_lock);
if (ctx->walk_control_obsolete) {
mutex_unlock(&ctx->walk_control_lock);
return -ECANCELED;
}
if (ctx->walk_control) {
mutex_unlock(&ctx->walk_control_lock);
return -EBUSY;
}
ctx->walk_control = control;
mutex_unlock(&ctx->walk_control_lock);
wait_for_completion(&control->completion);
if (control->canceled)
return -ECANCELED;
return 0;
}
static void kdamond_reset_aggregated(struct damon_ctx *c)
{
struct damon_target *t;
unsigned int ti = 0;
unsigned int nr_probes = 0;
struct damon_probe *probe;
if (trace_damon_region_aggregated_enabled()) {
damon_for_each_probe(probe, c)
nr_probes++;
}
damon_for_each_target(t, c) {
struct damon_region *r;
damon_for_each_region(r, t) {
int i;
trace_damon_aggregated(ti, r, damon_nr_regions(t));
trace_damon_region_aggregated(ti, r,
damon_nr_regions(t), nr_probes);
r->last_nr_accesses = r->nr_accesses;
r->nr_accesses = 0;
for (i = 0; i < DAMON_MAX_PROBES; i++) {
r->last_probe_hits[i] = r->probe_hits[i];
r->probe_hits[i] = 0;
}
}
ti++;
}
}
static unsigned long damon_get_intervals_score(struct damon_ctx *c)
{
struct damon_target *t;
struct damon_region *r;
unsigned long sz_region, max_access_events = 0, access_events = 0;
unsigned long target_access_events;
unsigned long goal_bp = c->attrs.intervals_goal.access_bp;
damon_for_each_target(t, c) {
damon_for_each_region(r, t) {
sz_region = damon_sz_region(r);
max_access_events += sz_region * c->attrs.aggr_samples;
access_events += sz_region * r->nr_accesses;
}
}
target_access_events = max_access_events * goal_bp / 10000;
target_access_events = target_access_events ? : 1;
return mult_frac(access_events, 10000, target_access_events);
}
static unsigned long damon_feed_loop_next_input(unsigned long last_input,
unsigned long score);
static unsigned long damon_get_intervals_adaptation_bp(struct damon_ctx *c)
{
unsigned long score_bp, adaptation_bp;
score_bp = damon_get_intervals_score(c);
adaptation_bp = damon_feed_loop_next_input(100000000, score_bp) /
10000;
if (adaptation_bp <= 10000)
adaptation_bp = 5000 + adaptation_bp / 2;
return adaptation_bp;
}
static noinline_for_stack void kdamond_tune_intervals(struct damon_ctx *c)
{
unsigned long adaptation_bp;
struct damon_attrs new_attrs;
struct damon_intervals_goal *goal;
adaptation_bp = damon_get_intervals_adaptation_bp(c);
if (adaptation_bp == 10000)
return;
new_attrs = c->attrs;
goal = &c->attrs.intervals_goal;
new_attrs.sample_interval = min(goal->max_sample_us,
c->attrs.sample_interval * adaptation_bp / 10000);
new_attrs.sample_interval = max(goal->min_sample_us,
new_attrs.sample_interval);
new_attrs.aggr_interval = new_attrs.sample_interval *
c->attrs.aggr_samples;
trace_damon_monitor_intervals_tune(new_attrs.sample_interval);
damon_set_attrs(c, &new_attrs);
}
static bool __damos_valid_target(struct damon_region *r, struct damos *s,
struct damon_ctx *c)
{
unsigned long sz;
unsigned int nr_accesses = damon_nr_accesses_mvsum(r, c);
sz = damon_sz_region(r);
return s->pattern.min_sz_region <= sz &&
sz <= s->pattern.max_sz_region &&
s->pattern.min_nr_accesses <= nr_accesses &&
nr_accesses <= s->pattern.max_nr_accesses &&
s->pattern.min_age_region <= r->age &&
r->age <= s->pattern.max_age_region;
}
static bool damos_quota_is_set(struct damos_quota *quota)
{
return quota->esz || quota->sz || quota->ms ||
!damos_quota_goals_empty(quota);
}
static bool damos_valid_target(struct damon_ctx *c, struct damon_region *r,
struct damos *s)
{
bool ret = __damos_valid_target(r, s, c);
if (!ret || !damos_quota_is_set(&s->quota) || !c->ops.get_scheme_score)
return ret;
return c->ops.get_scheme_score(c, r, s) >= s->quota.min_score;
}
static bool damos_skip_charged_region(struct damon_target *t,
struct damon_region *r, struct damos *s,
unsigned long min_region_sz)
{
struct damos_quota *quota = &s->quota;
unsigned long sz_to_skip;
bool skip = false;
if (quota->charge_target_from) {
if (t != quota->charge_target_from)
return true;
if (quota->charge_addr_from &&
r->ar.end <= quota->charge_addr_from) {
skip = true;
goto out;
}
if (quota->charge_addr_from && r->ar.start <
quota->charge_addr_from) {
sz_to_skip = ALIGN_DOWN(quota->charge_addr_from -
r->ar.start, min_region_sz);
if (!sz_to_skip) {
if (damon_sz_region(r) <= min_region_sz) {
skip = true;
goto out;
}
sz_to_skip = min_region_sz;
}
damon_split_region_at(t, r, sz_to_skip);
skip = true;
}
}
out:
if (r == damon_last_region(t)) {
quota->charge_target_from = NULL;
quota->charge_addr_from = 0;
}
return skip;
}
static void damos_update_stat(struct damos *s,
unsigned long sz_tried, unsigned long sz_applied,
unsigned long sz_ops_filter_passed)
{
s->stat.nr_tried++;
s->stat.sz_tried += sz_tried;
if (sz_applied)
s->stat.nr_applied++;
s->stat.sz_applied += sz_applied;
s->stat.sz_ops_filter_passed += sz_ops_filter_passed;
}
static bool damos_filter_match(struct damon_ctx *ctx, struct damon_target *t,
struct damon_region *r, struct damos_filter *filter,
unsigned long min_region_sz, int *err)
{
bool matched = false;
struct damon_target *ti;
int target_idx = 0;
unsigned long start, end, wsum;
*err = 0;
switch (filter->type) {
case DAMOS_FILTER_TYPE_TARGET:
damon_for_each_target(ti, ctx) {
if (ti == t)
break;
target_idx++;
}
matched = target_idx == filter->target_idx;
break;
case DAMOS_FILTER_TYPE_ADDR:
start = ALIGN_DOWN(filter->addr_range.start, min_region_sz);
end = ALIGN_DOWN(filter->addr_range.end, min_region_sz);
if (start <= r->ar.start && r->ar.end <= end) {
matched = true;
break;
}
if (r->ar.end <= start || end <= r->ar.start) {
matched = false;
break;
}
if (r->ar.start < start) {
*err = damon_split_region_at(t, r,
start - r->ar.start);
matched = false;
break;
}
*err = damon_split_region_at(t, r, end - r->ar.start);
matched = true;
break;
case DAMOS_FILTER_TYPE_PROBE_HITS_WSUM:
wsum = damon_probe_hits_wsum(r, false, true, ctx);
matched = filter->range_min <= wsum &&
wsum <= filter->range_max;
break;
default:
return false;
}
return matched == filter->matching;
}
static bool damos_core_filter_out(struct damon_ctx *ctx, struct damon_target *t,
struct damon_region *r, struct damos *s)
{
struct damos_filter *filter;
bool matching;
int err;
s->core_filters_allowed = false;
damos_for_each_core_filter(filter, s) {
matching = damos_filter_match(ctx, t, r, filter,
ctx->min_region_sz, &err);
if (err)
return true;
if (matching) {
if (filter->allow)
s->core_filters_allowed = true;
return !filter->allow;
}
}
return s->core_filters_default_reject;
}
static void damos_walk_call_walk(struct damon_ctx *ctx, struct damon_target *t,
struct damon_region *r, struct damos *s,
unsigned long sz_filter_passed)
{
struct damos_walk_control *control;
if (s->walk_completed)
return;
control = ctx->walk_control;
if (!control)
return;
control->walk_fn(control->data, ctx, t, r, s, sz_filter_passed);
}
static void damos_walk_complete(struct damon_ctx *ctx, struct damos *s)
{
struct damos *siter;
struct damos_walk_control *control;
control = ctx->walk_control;
if (!control)
return;
s->walk_completed = true;
damon_for_each_scheme(siter, ctx) {
if (!siter->walk_completed)
return;
}
damon_for_each_scheme(siter, ctx)
siter->walk_completed = false;
complete(&control->completion);
ctx->walk_control = NULL;
}
static void damos_walk_cancel(struct damon_ctx *ctx)
{
struct damos_walk_control *control;
mutex_lock(&ctx->walk_control_lock);
control = ctx->walk_control;
mutex_unlock(&ctx->walk_control_lock);
if (!control)
return;
control->canceled = true;
complete(&control->completion);
mutex_lock(&ctx->walk_control_lock);
ctx->walk_control = NULL;
mutex_unlock(&ctx->walk_control_lock);
}
static void damos_charge_quota(struct damos_quota *quota,
unsigned long sz_region, unsigned long sz_applied)
{
if (!quota->fail_charge_denom || sz_applied > sz_region)
quota->charged_sz += sz_region;
else
quota->charged_sz += sz_applied + mult_frac(
(sz_region - sz_applied),
quota->fail_charge_num,
quota->fail_charge_denom);
}
static bool damos_quota_is_full(struct damos_quota *quota,
unsigned long min_region_sz)
{
if (!damos_quota_is_set(quota))
return false;
if (quota->charged_sz >= quota->esz)
return true;
return quota->esz - quota->charged_sz < min_region_sz;
}
static void damos_apply_scheme(struct damon_ctx *c, struct damon_target *t,
struct damon_region *r, struct damos *s)
{
struct damos_quota *quota = &s->quota;
unsigned long sz = damon_sz_region(r);
struct timespec64 begin, end;
unsigned long sz_applied = 0;
unsigned long sz_ops_filter_passed = 0;
unsigned int cidx = 0;
struct damos *siter;
unsigned int sidx = 0;
struct damon_target *titer;
unsigned int tidx = 0, nr_accesses = 0;
bool do_trace = false;
if (trace_damos_before_apply_enabled()) {
damon_for_each_scheme(siter, c) {
if (siter == s)
break;
sidx++;
}
damon_for_each_target(titer, c) {
if (titer == t)
break;
tidx++;
}
nr_accesses = damon_nr_accesses_mvsum(r, c);
do_trace = true;
}
if (c->ops.apply_scheme) {
if (damos_quota_is_set(quota) &&
quota->charged_sz + sz > quota->esz) {
sz = ALIGN_DOWN(quota->esz - quota->charged_sz,
c->min_region_sz);
if (!sz)
goto update_stat;
if (damon_split_region_at(t, r, sz))
goto update_stat;
}
if (damos_core_filter_out(c, t, r, s))
return;
sz = damon_sz_region(r);
ktime_get_coarse_ts64(&begin);
trace_damos_before_apply(cidx, sidx, tidx, r, nr_accesses,
damon_nr_regions(t), do_trace);
sz_applied = c->ops.apply_scheme(c, t, r, s,
&sz_ops_filter_passed);
damos_walk_call_walk(c, t, r, s, sz_ops_filter_passed);
ktime_get_coarse_ts64(&end);
quota->total_charged_ns += timespec64_to_ns(&end) -
timespec64_to_ns(&begin);
damos_charge_quota(quota, sz, sz_applied);
if (damos_quota_is_full(quota, c->min_region_sz)) {
quota->charge_target_from = t;
quota->charge_addr_from = r->ar.end;
}
}
if (s->action != DAMOS_STAT)
r->age = 0;
update_stat:
damos_update_stat(s, sz, sz_applied, sz_ops_filter_passed);
}
static void damon_do_apply_schemes(struct damon_ctx *c,
struct damon_target *t,
struct damon_region *r)
{
struct damos *s;
damon_for_each_scheme(s, c) {
struct damos_quota *quota = &s->quota;
if (time_before(c->passed_sample_intervals, s->next_apply_sis))
continue;
if (!s->wmarks.activated)
continue;
if (damos_quota_is_full(quota, c->min_region_sz))
continue;
if (damos_skip_charged_region(t, r, s, c->min_region_sz))
continue;
if (s->max_nr_snapshots &&
s->max_nr_snapshots <= s->stat.nr_snapshots)
continue;
if (damos_valid_target(c, r, s))
damos_apply_scheme(c, t, r, s);
if (damon_is_last_region(r, t))
s->stat.nr_snapshots++;
}
}
static void damos_apply_target(struct damon_ctx *c, struct damon_target *t,
unsigned long max_region_sz)
{
struct damon_region *r;
damon_for_each_region(r, t) {
struct damon_region *prev_r;
damon_do_apply_schemes(c, t, r);
if (damon_first_region(t) == r)
continue;
prev_r = damon_prev_region(r);
if (prev_r->ar.end != r->ar.start)
continue;
if (prev_r->age != r->age)
continue;
if (prev_r->last_nr_accesses != r->last_nr_accesses)
continue;
if (prev_r->nr_accesses != r->nr_accesses)
continue;
if (r->ar.end - prev_r->ar.start > max_region_sz)
continue;
prev_r->ar.end = r->ar.end;
damon_destroy_region(r, t);
r = prev_r;
}
}
static unsigned long damon_feed_loop_next_input(unsigned long last_input,
unsigned long score)
{
const unsigned long goal = 10000;
const unsigned long min_input = 10000;
unsigned long score_goal_diff, compensation;
bool over_achieving = score > goal;
if (score == goal)
return last_input;
if (score >= goal * 2)
return min_input;
score_goal_diff = abs_diff(score, goal);
compensation = mult_frac(last_input, score_goal_diff, goal);
if (over_achieving)
return max(last_input - compensation, min_input);
if (last_input < ULONG_MAX - compensation)
return last_input + compensation;
return ULONG_MAX;
}
#ifdef CONFIG_PSI
static u64 damos_get_some_mem_psi_total(void)
{
if (static_branch_likely(&psi_disabled))
return 0;
return div_u64(psi_system.total[PSI_AVGS][PSI_MEM * 2],
NSEC_PER_USEC);
}
#else /* CONFIG_PSI */
static inline u64 damos_get_some_mem_psi_total(void)
{
return 0;
}
#endif /* CONFIG_PSI */
static void damos_set_psi_current_val(u64 now_psi_total,
struct damos_quota_goal *goal, struct damos *s)
{
u64 last_psi_total = goal->last_psi_total;
unsigned long val;
goal->last_psi_total = now_psi_total;
if (last_psi_total != U64_MAX) {
val = now_psi_total - last_psi_total;
if (goal->complement) {
if (val < s->quota.reset_interval * 1000)
val = s->quota.reset_interval * 1000 - val;
else
val = 0;
}
goal->current_value = val;
return;
}
if (s->quota.goal_tuner == DAMOS_QUOTA_GOAL_TUNER_CONSIST) {
goal->current_value = goal->target_value;
return;
}
if (!s->quota.esz)
goal->current_value = goal->target_value;
else
goal->current_value = 0;
}
#ifdef CONFIG_NUMA
static bool invalid_mem_node(int nid)
{
return nid < 0 || nid >= MAX_NUMNODES || !node_state(nid, N_MEMORY);
}
static __kernel_ulong_t damos_get_node_mem_bp(
struct damos_quota_goal *goal)
{
struct sysinfo i;
__kernel_ulong_t numerator;
if (invalid_mem_node(goal->nid)) {
if (goal->metric == DAMOS_QUOTA_NODE_MEM_USED_BP)
return 0;
else
return 10000;
}
si_meminfo_node(&i, goal->nid);
if (!i.totalram || i.totalram < i.freeram) {
if (goal->metric == DAMOS_QUOTA_NODE_MEM_USED_BP)
return 10000;
else
return 0;
}
if (goal->metric == DAMOS_QUOTA_NODE_MEM_USED_BP)
numerator = i.totalram - i.freeram;
else
numerator = i.freeram;
return mult_frac(numerator, 10000, i.totalram);
}
static unsigned long damos_get_node_memcg_used_bp(
struct damos_quota_goal *goal)
{
struct mem_cgroup *memcg;
struct lruvec *lruvec;
unsigned long used_pages, numerator;
struct sysinfo i;
if (invalid_mem_node(goal->nid)) {
if (goal->metric == DAMOS_QUOTA_NODE_MEMCG_USED_BP)
return 0;
else
return 10000;
}
memcg = mem_cgroup_get_from_id(goal->memcg_id);
if (!memcg) {
if (goal->metric == DAMOS_QUOTA_NODE_MEMCG_USED_BP)
return 0;
else
return 10000;
}
mem_cgroup_flush_stats(memcg);
lruvec = mem_cgroup_lruvec(memcg, NODE_DATA(goal->nid));
used_pages = lruvec_page_state(lruvec, NR_ACTIVE_ANON);
used_pages += lruvec_page_state(lruvec, NR_INACTIVE_ANON);
used_pages += lruvec_page_state(lruvec, NR_ACTIVE_FILE);
used_pages += lruvec_page_state(lruvec, NR_INACTIVE_FILE);
mem_cgroup_put(memcg);
si_meminfo_node(&i, goal->nid);
if (!i.totalram || i.totalram < used_pages) {
if (goal->metric == DAMOS_QUOTA_NODE_MEMCG_USED_BP)
return 10000;
else
return 0;
}
if (goal->metric == DAMOS_QUOTA_NODE_MEMCG_USED_BP)
numerator = used_pages;
else
numerator = i.totalram - used_pages;
return mult_frac(numerator, 10000, i.totalram);
}
#ifdef CONFIG_DAMON_PADDR
static phys_addr_t damos_calc_eligible_bytes(struct damon_ctx *c,
struct damos *s, int nid, phys_addr_t *total)
{
struct damon_target *t;
struct damon_region *r;
phys_addr_t total_eligible = 0;
phys_addr_t node_eligible = 0;
damon_for_each_target(t, c) {
damon_for_each_region(r, t) {
phys_addr_t addr, end_addr;
if (!__damos_valid_target(r, s, c))
continue;
addr = (phys_addr_t)r->ar.start * c->addr_unit;
end_addr = (phys_addr_t)r->ar.end * c->addr_unit;
while (addr < end_addr) {
struct folio *folio;
phys_addr_t folio_start, folio_end;
phys_addr_t overlap_start, overlap_end;
phys_addr_t counted;
folio = damon_get_folio(PHYS_PFN(addr));
if (!folio) {
addr = PAGE_ALIGN_DOWN(addr +
PAGE_SIZE);
if (!addr)
break;
continue;
}
folio_start = PFN_PHYS(folio_pfn(folio));
folio_end = folio_start + folio_size(folio);
overlap_start = max(addr, folio_start);
overlap_end = min(end_addr, folio_end);
if (overlap_end > overlap_start) {
counted = overlap_end - overlap_start;
total_eligible += counted;
if (folio_nid(folio) == nid)
node_eligible += counted;
}
addr = folio_end;
folio_put(folio);
}
cond_resched();
}
}
*total = total_eligible;
return node_eligible;
}
static unsigned long damos_get_node_eligible_mem_bp(struct damon_ctx *c,
struct damos *s, int nid)
{
phys_addr_t total_eligible = 0;
phys_addr_t node_eligible;
if (c->ops.id != DAMON_OPS_PADDR)
return 0;
if (nid < 0 || nid >= MAX_NUMNODES || !node_online(nid))
return 0;
node_eligible = damos_calc_eligible_bytes(c, s, nid, &total_eligible);
if (!(unsigned long)total_eligible)
return 0;
return mult_frac((unsigned long)node_eligible, 10000,
(unsigned long)total_eligible);
}
#else /* CONFIG_DAMON_PADDR */
static unsigned long damos_get_node_eligible_mem_bp(struct damon_ctx *c,
struct damos *s, int nid)
{
return 0;
}
#endif /* CONFIG_DAMON_PADDR */
#else /* CONFIG_NUMA */
static __kernel_ulong_t damos_get_node_mem_bp(
struct damos_quota_goal *goal)
{
return 0;
}
static unsigned long damos_get_node_memcg_used_bp(
struct damos_quota_goal *goal)
{
return 0;
}
static unsigned long damos_get_node_eligible_mem_bp(struct damon_ctx *c,
struct damos *s, int nid)
{
return 0;
}
#endif /* CONFIG_NUMA */
static unsigned int damos_get_in_active_mem_bp(bool active_ratio)
{
unsigned long active, inactive, total;
active = global_node_page_state(NR_LRU_BASE + LRU_ACTIVE_ANON) +
global_node_page_state(NR_LRU_BASE + LRU_ACTIVE_FILE);
inactive = global_node_page_state(NR_LRU_BASE + LRU_INACTIVE_ANON) +
global_node_page_state(NR_LRU_BASE + LRU_INACTIVE_FILE);
total = max(active + inactive, 1);
if (active_ratio)
return mult_frac(active, 10000, total);
return mult_frac(inactive, 10000, total);
}
static unsigned int damos_hugepage_mem_bp(void)
{
unsigned long thp, total_pages, free_pages;
total_pages = totalram_pages();
free_pages = global_zone_page_state(NR_FREE_PAGES);
if (total_pages <= free_pages)
return 10000;
thp = global_node_page_state(NR_ANON_THPS) +
global_node_page_state(NR_SHMEM_THPS) +
global_node_page_state(NR_FILE_THPS);
return mult_frac(thp, 10000, total_pages - free_pages);
}
static void damos_set_quota_goal_current_value(struct damon_ctx *c,
struct damos *s, struct damos_quota_goal *goal)
{
u64 now_psi_total;
switch (goal->metric) {
case DAMOS_QUOTA_USER_INPUT:
break;
case DAMOS_QUOTA_SOME_MEM_PSI_US:
now_psi_total = damos_get_some_mem_psi_total();
damos_set_psi_current_val(now_psi_total, goal, s);
break;
case DAMOS_QUOTA_NODE_MEM_USED_BP:
case DAMOS_QUOTA_NODE_MEM_FREE_BP:
goal->current_value = damos_get_node_mem_bp(goal);
break;
case DAMOS_QUOTA_NODE_MEMCG_USED_BP:
case DAMOS_QUOTA_NODE_MEMCG_FREE_BP:
goal->current_value = damos_get_node_memcg_used_bp(goal);
break;
case DAMOS_QUOTA_ACTIVE_MEM_BP:
case DAMOS_QUOTA_INACTIVE_MEM_BP:
goal->current_value = damos_get_in_active_mem_bp(
goal->metric == DAMOS_QUOTA_ACTIVE_MEM_BP);
break;
case DAMOS_QUOTA_NODE_ELIGIBLE_MEM_BP:
goal->current_value = damos_get_node_eligible_mem_bp(c, s,
goal->nid);
break;
case DAMOS_QUOTA_HUGEPAGE_MEM_BP:
goal->current_value = damos_hugepage_mem_bp();
break;
default:
break;
}
if (!goal->complement)
return;
if (goal->metric == DAMOS_QUOTA_USER_INPUT)
return;
if (goal->metric == DAMOS_QUOTA_SOME_MEM_PSI_US)
return;
if (goal->current_value < 10000)
goal->current_value = 10000 - goal->current_value;
else
goal->current_value = 0;
}
static unsigned long damos_quota_score(struct damon_ctx *c, struct damos *s)
{
struct damos_quota_goal *goal;
struct damos_quota *quota = &s->quota;
unsigned long highest_score = 0;
damos_for_each_quota_goal(goal, quota) {
damos_set_quota_goal_current_value(c, s, goal);
highest_score = max(highest_score,
mult_frac(goal->current_value, 10000,
goal->target_value));
}
return highest_score;
}
static void damos_goal_tune_esz_bp_consist(struct damon_ctx *c, struct damos *s)
{
struct damos_quota *quota = &s->quota;
unsigned long score = damos_quota_score(c, s);
quota->esz_bp = damon_feed_loop_next_input(
max(quota->esz_bp, 10000UL), score);
}
static void damos_goal_tune_esz_bp_temporal(struct damon_ctx *c,
struct damos *s)
{
struct damos_quota *quota = &s->quota;
unsigned long score = damos_quota_score(c, s);
if (score >= 10000)
quota->esz_bp = 0;
else if (quota->sz && quota->sz <= ULONG_MAX / 10000)
quota->esz_bp = quota->sz * 10000;
else
quota->esz_bp = ULONG_MAX;
}
static void damos_set_effective_quota(struct damon_ctx *ctx, struct damos *s)
{
struct damos_quota *quota = &s->quota;
unsigned long throughput;
unsigned long esz = ULONG_MAX;
unsigned long esz_time;
if (!quota->ms && list_empty("a->goals)) {
quota->esz = quota->sz;
return;
}
if (!list_empty("a->goals)) {
if (quota->goal_tuner == DAMOS_QUOTA_GOAL_TUNER_CONSIST)
damos_goal_tune_esz_bp_consist(ctx, s);
else if (quota->goal_tuner == DAMOS_QUOTA_GOAL_TUNER_TEMPORAL)
damos_goal_tune_esz_bp_temporal(ctx, s);
esz = quota->esz_bp / 10000;
}
if (quota->ms) {
if (quota->total_charged_ns)
throughput = mult_frac(quota->total_charged_sz,
1000000, quota->total_charged_ns);
else
throughput = PAGE_SIZE * 1024;
esz_time = max(throughput * quota->ms, ctx->min_region_sz);
esz = min(esz_time, esz);
}
if (quota->sz && quota->sz < esz)
esz = quota->sz;
quota->esz = esz;
}
static void damos_trace_esz(struct damon_ctx *c, struct damos *s,
struct damos_quota *quota)
{
unsigned int cidx = 0, sidx = 0;
struct damos *siter;
damon_for_each_scheme(siter, c) {
if (siter == s)
break;
sidx++;
}
trace_damos_esz(cidx, sidx, quota->esz);
}
static void damos_fix_stale_charge_pointers(struct damon_ctx *c,
struct damos *s)
{
struct damos_quota *quota;
struct damon_target *t;
quota = &s->quota;
if (!quota->charge_target_from)
return;
damon_for_each_target(t, c) {
if (t == quota->charge_target_from) {
if (damon_nr_regions(t) > 0)
return;
break;
}
}
quota->charge_target_from = NULL;
quota->charge_addr_from = 0;
}
static void damos_adjust_quota(struct damon_ctx *c, struct damos *s)
{
struct damos_quota *quota = &s->quota;
struct damon_target *t;
struct damon_region *r;
unsigned long cumulated_sz, cached_esz;
unsigned int score, max_score = 0;
if (!damos_quota_is_set(quota))
return;
if (!quota->total_charged_sz && !quota->charged_from) {
quota->charged_from = jiffies;
damos_set_effective_quota(c, s);
if (trace_damos_esz_enabled())
damos_trace_esz(c, s, quota);
}
if (!time_in_range_open(jiffies, quota->charged_from,
quota->charged_from +
msecs_to_jiffies(quota->reset_interval))) {
if (damos_quota_is_full(quota, c->min_region_sz))
s->stat.qt_exceeds++;
quota->total_charged_sz += quota->charged_sz;
quota->charged_from = jiffies;
quota->charged_sz = 0;
if (trace_damos_esz_enabled())
cached_esz = quota->esz;
damos_set_effective_quota(c, s);
if (trace_damos_esz_enabled() && quota->esz != cached_esz)
damos_trace_esz(c, s, quota);
}
damos_fix_stale_charge_pointers(c, s);
if (damos_quota_is_full(quota, c->min_region_sz))
return;
if (!c->ops.get_scheme_score)
return;
memset(c->regions_score_histogram, 0,
sizeof(*c->regions_score_histogram) *
(DAMOS_MAX_SCORE + 1));
damon_for_each_target(t, c) {
damon_for_each_region(r, t) {
if (!__damos_valid_target(r, s, c))
continue;
if (damos_core_filter_out(c, t, r, s))
continue;
score = c->ops.get_scheme_score(c, r, s);
c->regions_score_histogram[score] +=
damon_sz_region(r);
if (score > max_score)
max_score = score;
}
}
for (cumulated_sz = 0, score = max_score; ; score--) {
cumulated_sz += c->regions_score_histogram[score];
if (cumulated_sz >= quota->esz || !score)
break;
}
quota->min_score = score;
}
static void damos_trace_stat(struct damon_ctx *c, struct damos *s)
{
unsigned int cidx = 0, sidx = 0;
struct damos *siter;
if (!trace_damos_stat_after_apply_interval_enabled())
return;
damon_for_each_scheme(siter, c) {
if (siter == s)
break;
sidx++;
}
trace_call__damos_stat_after_apply_interval(cidx, sidx, &s->stat);
}
static noinline_for_stack void kdamond_apply_schemes(struct damon_ctx *c)
{
struct damon_target *t;
struct damos *s;
bool has_schemes_to_apply = false;
unsigned long max_region_sz;
damon_for_each_scheme(s, c) {
if (time_before(c->passed_sample_intervals, s->next_apply_sis))
continue;
if (!s->wmarks.activated)
continue;
has_schemes_to_apply = true;
damos_adjust_quota(c, s);
}
if (!has_schemes_to_apply)
return;
max_region_sz = damon_region_sz_limit(c);
mutex_lock(&c->walk_control_lock);
damon_for_each_target(t, c) {
if (c->ops.target_valid && c->ops.target_valid(t) == false) {
damon_for_each_scheme(s, c) {
if (s->quota.charge_target_from != t)
continue;
s->quota.charge_target_from = NULL;
s->quota.charge_addr_from = 0;
}
continue;
}
damos_apply_target(c, t, max_region_sz);
}
damon_for_each_scheme(s, c) {
if (time_before(c->passed_sample_intervals, s->next_apply_sis))
continue;
damos_walk_complete(c, s);
damos_set_next_apply_sis(s, c);
s->last_applied = NULL;
damos_trace_stat(c, s);
}
mutex_unlock(&c->walk_control_lock);
}
#ifdef CONFIG_DAMON_DEBUG_SANITY
static void damon_verify_merge_two_regions(
struct damon_region *l, struct damon_region *r)
{
WARN_ONCE(l->ar.start >= l->ar.end, "l: %lu-%lu, r: %lu-%lu\n",
l->ar.start, l->ar.end, r->ar.start, r->ar.end);
}
#else
static void damon_verify_merge_two_regions(
struct damon_region *l, struct damon_region *r)
{
}
#endif
static void damon_merge_two_regions(struct damon_target *t,
struct damon_region *l, struct damon_region *r)
{
unsigned long sz_l = damon_sz_region(l), sz_r = damon_sz_region(r);
int i;
l->nr_accesses = (l->nr_accesses * sz_l + r->nr_accesses * sz_r) /
(sz_l + sz_r);
l->age = (l->age * sz_l + r->age * sz_r) / (sz_l + sz_r);
l->ar.end = r->ar.end;
for (i = 0; i < DAMON_MAX_PROBES; i++)
l->probe_hits[i] = (l->probe_hits[i] * sz_l + r->probe_hits[i]
* sz_r) / (sz_l + sz_r);
damon_verify_merge_two_regions(l, r);
damon_destroy_region(r, t);
}
static unsigned int damon_merge_score(struct damon_region *r, bool last,
struct damon_ctx *ctx, bool use_probe_hits)
{
if (use_probe_hits)
return damon_probe_hits_wsum(r, last, false, ctx);
if (last)
return r->last_nr_accesses;
return r->nr_accesses;
}
static void damon_merge_regions_of(struct damon_target *t, unsigned int thres,
unsigned long sz_limit, struct damon_ctx *ctx, bool count_age)
{
struct damon_region *r, *prev = NULL, *next;
bool use_probe_hits = damon_has_probe_weights(ctx);
damon_for_each_region_safe(r, next, t) {
unsigned int score, last_score, diff;
score = damon_merge_score(r, false, ctx, use_probe_hits);
last_score = damon_merge_score(r, true, ctx, use_probe_hits);
if (count_age) {
if (abs_diff(score, last_score) > thres)
r->age = 0;
else if ((score == 0) != (last_score == 0))
r->age = 0;
else
r->age++;
}
if (!prev)
goto set_prev_continue;
if (prev->ar.end != r->ar.start)
goto set_prev_continue;
diff = abs_diff(score, damon_merge_score(prev, false, ctx,
use_probe_hits));
if (diff > thres)
goto set_prev_continue;
if (damon_sz_region(prev) + damon_sz_region(r) > sz_limit)
goto set_prev_continue;
damon_merge_two_regions(t, prev, r);
continue;
set_prev_continue:
prev = r;
}
}
static noinline_for_stack void kdamond_merge_regions(struct damon_ctx *c,
unsigned int threshold,
unsigned long sz_limit)
{
struct damon_target *t;
unsigned int nr_regions;
unsigned int max_thres;
bool count_age = true;
max_thres = damon_nr_samples_per_aggr(&c->attrs);
while (true) {
nr_regions = 0;
damon_for_each_target(t, c) {
damon_merge_regions_of(t, threshold, sz_limit, c,
count_age);
nr_regions += damon_nr_regions(t);
}
count_age = false;
if (nr_regions <= c->attrs.max_nr_regions ||
max_thres <= threshold)
break;
if (threshold < max_thres / 2)
threshold = max(1, threshold * 2);
else
threshold = max_thres;
}
}
#ifdef CONFIG_DAMON_DEBUG_SANITY
static void damon_verify_split_region_at(struct damon_region *r,
unsigned long sz_r)
{
WARN_ONCE(sz_r == 0 || sz_r >= damon_sz_region(r),
"sz_r: %lu r: %lu-%lu (%lu)\n",
sz_r, r->ar.start, r->ar.end, damon_sz_region(r));
}
#else
static void damon_verify_split_region_at(struct damon_region *r,
unsigned long sz_r)
{
}
#endif
static int damon_split_region_at(struct damon_target *t,
struct damon_region *r, unsigned long sz_r)
{
struct damon_region *new;
damon_verify_split_region_at(r, sz_r);
new = damon_new_region(r->ar.start + sz_r, r->ar.end);
if (!new)
return -ENOMEM;
r->ar.end = new->ar.start;
new->age = r->age;
new->last_nr_accesses = r->last_nr_accesses;
new->nr_accesses = r->nr_accesses;
memcpy(new->probe_hits, r->probe_hits, sizeof(r->probe_hits));
memcpy(new->last_probe_hits, r->last_probe_hits,
sizeof(r->last_probe_hits));
damon_insert_region(new, r, damon_next_region(r), t);
return 0;
}
static void damon_split_regions_of(struct damon_ctx *ctx,
struct damon_target *t, int nr_subs,
unsigned long min_region_sz)
{
struct damon_region *r, *next;
unsigned long sz_region, sz_sub = 0;
int i;
damon_for_each_region_safe(r, next, t) {
sz_region = damon_sz_region(r);
for (i = 0; i < nr_subs - 1 &&
sz_region > 2 * min_region_sz; i++) {
sz_sub = ALIGN_DOWN(damon_rand(ctx, 1, 10) *
sz_region / 10, min_region_sz);
if (sz_sub == 0 || sz_sub >= sz_region)
continue;
damon_split_region_at(t, r, sz_sub);
sz_region = sz_sub;
}
}
}
static void damon_split_some_regions(struct damon_ctx *ctx,
unsigned long split_step)
{
struct damon_target *t;
struct damon_region *r, *next;
unsigned long offset;
unsigned long idx = 0;
offset = ctx->region_split_rotation++ % split_step;
damon_for_each_target(t, ctx) {
damon_for_each_region_safe(r, next, t) {
unsigned long sz_region, sz_sub;
if (idx++ % split_step != offset)
continue;
sz_region = damon_sz_region(r);
if (sz_region < 2 * ctx->min_region_sz)
continue;
sz_sub = ALIGN_DOWN(damon_rand(ctx, 1, 10) *
sz_region / 10, ctx->min_region_sz);
if (sz_sub == 0 || sz_sub >= sz_region)
continue;
damon_split_region_at(t, r, sz_sub);
}
}
}
static noinline_for_stack void kdamond_split_regions(struct damon_ctx *ctx)
{
struct damon_target *t;
unsigned long nr_regions = 0;
unsigned long max_nr_regions = ctx->attrs.max_nr_regions;
int nr_subregions = 2;
damon_for_each_target(t, ctx)
nr_regions += damon_nr_regions(t);
if (nr_regions >= max_nr_regions)
goto done;
if (nr_regions > max_nr_regions / 2) {
damon_split_some_regions(ctx,
max_nr_regions / (max_nr_regions - nr_regions));
goto done;
}
if (ctx->last_nr_regions == nr_regions &&
nr_regions < max_nr_regions / 3)
nr_subregions = 3;
damon_for_each_target(t, ctx)
damon_split_regions_of(ctx, t, nr_subregions,
ctx->min_region_sz);
done:
ctx->last_nr_regions = nr_regions;
}
static bool kdamond_need_stop(struct damon_ctx *ctx)
{
struct damon_target *t;
if (kthread_should_stop())
return true;
if (!ctx->ops.target_valid)
return false;
damon_for_each_target(t, ctx) {
if (ctx->ops.target_valid(t))
return false;
}
return true;
}
static int damos_get_wmark_metric_value(enum damos_wmark_metric metric,
unsigned long *metric_value)
{
switch (metric) {
case DAMOS_WMARK_FREE_MEM_RATE:
*metric_value = global_zone_page_state(NR_FREE_PAGES) * 1000 /
totalram_pages();
return 0;
default:
break;
}
return -EINVAL;
}
static unsigned long damos_wmark_wait_us(struct damos *scheme)
{
unsigned long metric;
if (damos_get_wmark_metric_value(scheme->wmarks.metric, &metric))
return 0;
if (metric > scheme->wmarks.high || scheme->wmarks.low > metric) {
scheme->wmarks.activated = false;
return scheme->wmarks.interval;
}
if ((scheme->wmarks.high >= metric && metric >= scheme->wmarks.mid) &&
!scheme->wmarks.activated)
return scheme->wmarks.interval;
scheme->wmarks.activated = true;
return 0;
}
static void kdamond_usleep(unsigned long usecs)
{
if (usecs >= USLEEP_RANGE_UPPER_BOUND)
schedule_timeout_idle(usecs_to_jiffies(usecs));
else
usleep_range_idle(usecs, usecs + 1);
}
#ifdef CONFIG_DAMON_DEBUG_SANITY
static void damon_verify_ctx(struct damon_ctx *c)
{
struct damon_target *t;
struct damon_region *r;
damon_for_each_target(t, c) {
struct damon_region *prev_r = NULL;
unsigned int nr_regions = 0;
damon_for_each_region(r, t) {
WARN_ONCE(r->ar.start >= r->ar.end,
"region start (%lu) >= end (%lu)\n",
r->ar.start, r->ar.end);
WARN_ONCE(prev_r && prev_r->ar.end > r->ar.start,
"region overlap (%lu > %lu)\n",
prev_r->ar.end, r->ar.start);
prev_r = r;
nr_regions++;
}
WARN_ONCE(damon_nr_regions(t) != nr_regions,
"nr_regions mismatch: %u != %u\n",
damon_nr_regions(t), nr_regions);
}
}
#else
static void damon_verify_ctx(struct damon_ctx *c)
{
}
#endif
static void kdamond_call(struct damon_ctx *ctx, bool cancel)
{
struct damon_call_control *control, *next;
LIST_HEAD(controls);
damon_verify_ctx(ctx);
mutex_lock(&ctx->call_controls_lock);
list_splice_tail_init(&ctx->call_controls, &controls);
mutex_unlock(&ctx->call_controls_lock);
list_for_each_entry_safe(control, next, &controls, list) {
if (!control->repeat || cancel)
list_del(&control->list);
if (cancel)
control->canceled = true;
else
control->return_code = control->fn(control->data);
if (!control->repeat)
complete(&control->completion);
else if (control->canceled && control->dealloc_on_cancel)
kfree(control);
if (!cancel && ctx->maybe_corrupted)
break;
}
mutex_lock(&ctx->call_controls_lock);
list_splice_tail(&controls, &ctx->call_controls);
mutex_unlock(&ctx->call_controls_lock);
}
static int kdamond_wait_activation(struct damon_ctx *ctx)
{
struct damos *s;
unsigned long wait_time;
unsigned long min_wait_time = 0;
bool init_wait_time = false;
while (!kdamond_need_stop(ctx)) {
damon_for_each_scheme(s, ctx) {
wait_time = damos_wmark_wait_us(s);
if (!init_wait_time || wait_time < min_wait_time) {
init_wait_time = true;
min_wait_time = wait_time;
}
}
if (!min_wait_time)
return 0;
kdamond_usleep(min_wait_time);
kdamond_call(ctx, false);
if (ctx->maybe_corrupted)
return -EINVAL;
damos_walk_cancel(ctx);
}
return -EBUSY;
}
static void kdamond_init_ctx(struct damon_ctx *ctx)
{
unsigned long sample_interval = ctx->attrs.sample_interval ?
ctx->attrs.sample_interval : 1;
struct damos *scheme;
ctx->passed_sample_intervals = 0;
ctx->next_aggregation_sis = ctx->attrs.aggr_interval / sample_interval;
ctx->next_ops_update_sis = ctx->attrs.ops_update_interval /
sample_interval;
ctx->next_intervals_tune_sis = ctx->next_aggregation_sis *
ctx->attrs.intervals_goal.aggrs;
damon_for_each_scheme(scheme, ctx) {
damos_set_next_apply_sis(scheme, ctx);
damos_set_filters_default_reject(scheme);
}
}
static int kdamond_fn(void *data)
{
struct damon_ctx *ctx = data;
unsigned long sz_limit = 0;
mutex_lock(&ctx->call_controls_lock);
ctx->call_controls_obsolete = false;
mutex_unlock(&ctx->call_controls_lock);
mutex_lock(&ctx->walk_control_lock);
ctx->walk_control_obsolete = false;
mutex_unlock(&ctx->walk_control_lock);
complete(&ctx->kdamond_started);
kdamond_init_ctx(ctx);
if (ctx->ops.init)
ctx->ops.init(ctx);
ctx->regions_score_histogram = kmalloc_objs(*ctx->regions_score_histogram,
DAMOS_MAX_SCORE + 1);
if (!ctx->regions_score_histogram)
goto done;
sz_limit = damon_apply_min_nr_regions(ctx);
while (!kdamond_need_stop(ctx)) {
unsigned long next_aggregation_sis = ctx->next_aggregation_sis;
unsigned long next_ops_update_sis = ctx->next_ops_update_sis;
unsigned long sample_interval = ctx->attrs.sample_interval;
bool access_check_disabled = damon_has_probe_weights(ctx);
bool do_prep;
unsigned int max_merge_score = 0, max_wsum;
bool get_max_wsum;
if (kdamond_wait_activation(ctx))
break;
do_prep = ctx->ops.prep_probes && damon_has_prep(ctx);
if (!access_check_disabled && ctx->ops.prepare_access_checks)
ctx->ops.prepare_access_checks(ctx);
if (do_prep)
ctx->ops.prep_probes(ctx, access_check_disabled);
kdamond_usleep(sample_interval);
ctx->passed_sample_intervals++;
if (!access_check_disabled && ctx->ops.check_accesses)
max_merge_score = ctx->ops.check_accesses(ctx);
if (ctx->ops.apply_probes) {
if (time_after_eq(ctx->passed_sample_intervals,
next_aggregation_sis) &&
access_check_disabled)
get_max_wsum = true;
else
get_max_wsum = false;
max_wsum = ctx->ops.apply_probes(ctx,
access_check_disabled && !do_prep,
get_max_wsum);
if (get_max_wsum)
max_merge_score = max_wsum;
}
if (time_after_eq(ctx->passed_sample_intervals,
next_aggregation_sis)) {
kdamond_merge_regions(ctx,
max_merge_score / 10,
sz_limit);
sz_limit = damon_apply_min_nr_regions(ctx);
}
kdamond_call(ctx, false);
if (ctx->maybe_corrupted)
break;
while (ctx->pause) {
damos_walk_cancel(ctx);
kdamond_usleep(ctx->attrs.sample_interval);
kdamond_call(ctx, false);
if (kdamond_need_stop(ctx) || ctx->maybe_corrupted)
goto done;
}
if (!list_empty(&ctx->schemes))
kdamond_apply_schemes(ctx);
else
damos_walk_cancel(ctx);
sample_interval = ctx->attrs.sample_interval ?
ctx->attrs.sample_interval : 1;
if (time_after_eq(ctx->passed_sample_intervals,
next_aggregation_sis)) {
if (ctx->attrs.intervals_goal.aggrs &&
time_after_eq(
ctx->passed_sample_intervals,
ctx->next_intervals_tune_sis)) {
ctx->next_aggregation_sis =
next_aggregation_sis;
ctx->next_intervals_tune_sis +=
ctx->attrs.aggr_samples *
ctx->attrs.intervals_goal.aggrs;
kdamond_tune_intervals(ctx);
sample_interval = ctx->attrs.sample_interval ?
ctx->attrs.sample_interval : 1;
}
ctx->next_aggregation_sis = next_aggregation_sis +
ctx->attrs.aggr_interval / sample_interval;
kdamond_reset_aggregated(ctx);
kdamond_split_regions(ctx);
}
if (time_after_eq(ctx->passed_sample_intervals,
next_ops_update_sis)) {
ctx->next_ops_update_sis = next_ops_update_sis +
ctx->attrs.ops_update_interval /
sample_interval;
if (ctx->ops.update)
ctx->ops.update(ctx);
}
}
done:
damon_destroy_targets(ctx);
kfree(ctx->regions_score_histogram);
mutex_lock(&ctx->call_controls_lock);
ctx->call_controls_obsolete = true;
mutex_unlock(&ctx->call_controls_lock);
kdamond_call(ctx, true);
mutex_lock(&ctx->walk_control_lock);
ctx->walk_control_obsolete = true;
mutex_unlock(&ctx->walk_control_lock);
damos_walk_cancel(ctx);
mutex_lock(&ctx->kdamond_lock);
ctx->kdamond = NULL;
mutex_unlock(&ctx->kdamond_lock);
mutex_lock(&damon_lock);
nr_running_ctxs--;
if (!nr_running_ctxs && running_exclusive_ctxs)
running_exclusive_ctxs = false;
mutex_unlock(&damon_lock);
return 0;
}
struct damon_system_ram_range_walk_arg {
bool walked;
struct resource res;
};
static int damon_system_ram_walk_fn(struct resource *res, void *arg)
{
struct damon_system_ram_range_walk_arg *a = arg;
if (!a->walked) {
a->walked = true;
a->res.start = res->start;
}
a->res.end = res->end;
return 0;
}
static unsigned long damon_res_to_core_addr(resource_size_t ra,
unsigned long addr_unit)
{
if (sizeof(ra) == 8 && sizeof(addr_unit) == 4)
return div_u64(ra, addr_unit);
return ra / addr_unit;
}
static bool damon_find_system_rams_range(unsigned long *start,
unsigned long *end, unsigned long addr_unit)
{
struct damon_system_ram_range_walk_arg arg = {};
walk_system_ram_res(0, -1, &arg, damon_system_ram_walk_fn);
if (!arg.walked)
return false;
*start = damon_res_to_core_addr(arg.res.start, addr_unit);
*end = damon_res_to_core_addr(arg.res.end + 1, addr_unit);
if (*end <= *start)
return false;
return true;
}
int damon_set_region_system_rams_default(struct damon_target *t,
unsigned long *start, unsigned long *end,
unsigned long addr_unit, unsigned long min_region_sz)
{
struct damon_addr_range addr_range;
if (!*start && !*end &&
!damon_find_system_rams_range(start, end, addr_unit))
return -EINVAL;
addr_range.start = *start;
addr_range.end = *end;
return damon_set_regions(t, &addr_range, 1, min_region_sz);
}
void damon_update_region_access_rate(struct damon_region *r, bool accessed)
{
if (accessed)
r->nr_accesses++;
}
bool damon_initialized(void)
{
return damon_region_cache != NULL;
}
static int __init damon_init(void)
{
damon_region_cache = KMEM_CACHE(damon_region, 0);
if (unlikely(!damon_region_cache)) {
pr_err("creating damon_region_cache fails\n");
return -ENOMEM;
}
return 0;
}
subsys_initcall(damon_init);
#include "tests/core-kunit.h"