xref: /openbmc/linux/mm/damon/core.c (revision 5f1fc67f)
12224d848SSeongJae Park // SPDX-License-Identifier: GPL-2.0
22224d848SSeongJae Park /*
32224d848SSeongJae Park  * Data Access Monitor
42224d848SSeongJae Park  *
52224d848SSeongJae Park  * Author: SeongJae Park <sjpark@amazon.de>
62224d848SSeongJae Park  */
72224d848SSeongJae Park 
82224d848SSeongJae Park #define pr_fmt(fmt) "damon: " fmt
92224d848SSeongJae Park 
102224d848SSeongJae Park #include <linux/damon.h>
112224d848SSeongJae Park #include <linux/delay.h>
122224d848SSeongJae Park #include <linux/kthread.h>
13ee801b7dSSeongJae Park #include <linux/mm.h>
142224d848SSeongJae Park #include <linux/slab.h>
1538683e00SSeongJae Park #include <linux/string.h>
162224d848SSeongJae Park 
172fcb9362SSeongJae Park #define CREATE_TRACE_POINTS
182fcb9362SSeongJae Park #include <trace/events/damon.h>
192fcb9362SSeongJae Park 
2017ccae8bSSeongJae Park #ifdef CONFIG_DAMON_KUNIT_TEST
2117ccae8bSSeongJae Park #undef DAMON_MIN_REGION
2217ccae8bSSeongJae Park #define DAMON_MIN_REGION 1
2317ccae8bSSeongJae Park #endif
2417ccae8bSSeongJae Park 
252224d848SSeongJae Park static DEFINE_MUTEX(damon_lock);
262224d848SSeongJae Park static int nr_running_ctxs;
278b9b0d33SSeongJae Park static bool running_exclusive_ctxs;
282224d848SSeongJae Park 
299f7b053aSSeongJae Park static DEFINE_MUTEX(damon_ops_lock);
309f7b053aSSeongJae Park static struct damon_operations damon_registered_ops[NR_DAMON_OPS];
319f7b053aSSeongJae Park 
32a1870944SDawei Li static struct kmem_cache *damon_region_cache __ro_after_init;
33a1870944SDawei Li 
349f7b053aSSeongJae Park /* Should be called under damon_ops_lock with id smaller than NR_DAMON_OPS */
35152e5617SSeongJae Park static bool __damon_is_registered_ops(enum damon_ops_id id)
369f7b053aSSeongJae Park {
379f7b053aSSeongJae Park 	struct damon_operations empty_ops = {};
389f7b053aSSeongJae Park 
399f7b053aSSeongJae Park 	if (!memcmp(&empty_ops, &damon_registered_ops[id], sizeof(empty_ops)))
409f7b053aSSeongJae Park 		return false;
419f7b053aSSeongJae Park 	return true;
429f7b053aSSeongJae Park }
439f7b053aSSeongJae Park 
449f7b053aSSeongJae Park /**
45152e5617SSeongJae Park  * damon_is_registered_ops() - Check if a given damon_operations is registered.
46152e5617SSeongJae Park  * @id:	Id of the damon_operations to check if registered.
47152e5617SSeongJae Park  *
48152e5617SSeongJae Park  * Return: true if the ops is set, false otherwise.
49152e5617SSeongJae Park  */
50152e5617SSeongJae Park bool damon_is_registered_ops(enum damon_ops_id id)
51152e5617SSeongJae Park {
52152e5617SSeongJae Park 	bool registered;
53152e5617SSeongJae Park 
54152e5617SSeongJae Park 	if (id >= NR_DAMON_OPS)
55152e5617SSeongJae Park 		return false;
56152e5617SSeongJae Park 	mutex_lock(&damon_ops_lock);
57152e5617SSeongJae Park 	registered = __damon_is_registered_ops(id);
58152e5617SSeongJae Park 	mutex_unlock(&damon_ops_lock);
59152e5617SSeongJae Park 	return registered;
60152e5617SSeongJae Park }
61152e5617SSeongJae Park 
62152e5617SSeongJae Park /**
639f7b053aSSeongJae Park  * damon_register_ops() - Register a monitoring operations set to DAMON.
649f7b053aSSeongJae Park  * @ops:	monitoring operations set to register.
659f7b053aSSeongJae Park  *
669f7b053aSSeongJae Park  * This function registers a monitoring operations set of valid &struct
679f7b053aSSeongJae Park  * damon_operations->id so that others can find and use them later.
689f7b053aSSeongJae Park  *
699f7b053aSSeongJae Park  * Return: 0 on success, negative error code otherwise.
709f7b053aSSeongJae Park  */
719f7b053aSSeongJae Park int damon_register_ops(struct damon_operations *ops)
729f7b053aSSeongJae Park {
739f7b053aSSeongJae Park 	int err = 0;
749f7b053aSSeongJae Park 
759f7b053aSSeongJae Park 	if (ops->id >= NR_DAMON_OPS)
769f7b053aSSeongJae Park 		return -EINVAL;
779f7b053aSSeongJae Park 	mutex_lock(&damon_ops_lock);
789f7b053aSSeongJae Park 	/* Fail for already registered ops */
79152e5617SSeongJae Park 	if (__damon_is_registered_ops(ops->id)) {
809f7b053aSSeongJae Park 		err = -EINVAL;
819f7b053aSSeongJae Park 		goto out;
829f7b053aSSeongJae Park 	}
839f7b053aSSeongJae Park 	damon_registered_ops[ops->id] = *ops;
849f7b053aSSeongJae Park out:
859f7b053aSSeongJae Park 	mutex_unlock(&damon_ops_lock);
869f7b053aSSeongJae Park 	return err;
879f7b053aSSeongJae Park }
889f7b053aSSeongJae Park 
899f7b053aSSeongJae Park /**
909f7b053aSSeongJae Park  * damon_select_ops() - Select a monitoring operations to use with the context.
919f7b053aSSeongJae Park  * @ctx:	monitoring context to use the operations.
929f7b053aSSeongJae Park  * @id:		id of the registered monitoring operations to select.
939f7b053aSSeongJae Park  *
949f7b053aSSeongJae Park  * This function finds registered monitoring operations set of @id and make
959f7b053aSSeongJae Park  * @ctx to use it.
969f7b053aSSeongJae Park  *
979f7b053aSSeongJae Park  * Return: 0 on success, negative error code otherwise.
989f7b053aSSeongJae Park  */
999f7b053aSSeongJae Park int damon_select_ops(struct damon_ctx *ctx, enum damon_ops_id id)
1009f7b053aSSeongJae Park {
1019f7b053aSSeongJae Park 	int err = 0;
1029f7b053aSSeongJae Park 
1039f7b053aSSeongJae Park 	if (id >= NR_DAMON_OPS)
1049f7b053aSSeongJae Park 		return -EINVAL;
1059f7b053aSSeongJae Park 
1069f7b053aSSeongJae Park 	mutex_lock(&damon_ops_lock);
107152e5617SSeongJae Park 	if (!__damon_is_registered_ops(id))
1089f7b053aSSeongJae Park 		err = -EINVAL;
1099f7b053aSSeongJae Park 	else
1109f7b053aSSeongJae Park 		ctx->ops = damon_registered_ops[id];
1119f7b053aSSeongJae Park 	mutex_unlock(&damon_ops_lock);
1129f7b053aSSeongJae Park 	return err;
1139f7b053aSSeongJae Park }
1149f7b053aSSeongJae Park 
115f23b8eeeSSeongJae Park /*
116f23b8eeeSSeongJae Park  * Construct a damon_region struct
117f23b8eeeSSeongJae Park  *
118f23b8eeeSSeongJae Park  * Returns the pointer to the new struct if success, or NULL otherwise
119f23b8eeeSSeongJae Park  */
120f23b8eeeSSeongJae Park struct damon_region *damon_new_region(unsigned long start, unsigned long end)
121f23b8eeeSSeongJae Park {
122f23b8eeeSSeongJae Park 	struct damon_region *region;
123f23b8eeeSSeongJae Park 
124a1870944SDawei Li 	region = kmem_cache_alloc(damon_region_cache, GFP_KERNEL);
125f23b8eeeSSeongJae Park 	if (!region)
126f23b8eeeSSeongJae Park 		return NULL;
127f23b8eeeSSeongJae Park 
128f23b8eeeSSeongJae Park 	region->ar.start = start;
129f23b8eeeSSeongJae Park 	region->ar.end = end;
130f23b8eeeSSeongJae Park 	region->nr_accesses = 0;
131f23b8eeeSSeongJae Park 	INIT_LIST_HEAD(&region->list);
132f23b8eeeSSeongJae Park 
133fda504faSSeongJae Park 	region->age = 0;
134fda504faSSeongJae Park 	region->last_nr_accesses = 0;
135fda504faSSeongJae Park 
136f23b8eeeSSeongJae Park 	return region;
137f23b8eeeSSeongJae Park }
138f23b8eeeSSeongJae Park 
139f23b8eeeSSeongJae Park void damon_add_region(struct damon_region *r, struct damon_target *t)
140f23b8eeeSSeongJae Park {
141f23b8eeeSSeongJae Park 	list_add_tail(&r->list, &t->regions_list);
142b9a6ac4eSSeongJae Park 	t->nr_regions++;
143f23b8eeeSSeongJae Park }
144f23b8eeeSSeongJae Park 
145b9a6ac4eSSeongJae Park static void damon_del_region(struct damon_region *r, struct damon_target *t)
146f23b8eeeSSeongJae Park {
147f23b8eeeSSeongJae Park 	list_del(&r->list);
148b9a6ac4eSSeongJae Park 	t->nr_regions--;
149f23b8eeeSSeongJae Park }
150f23b8eeeSSeongJae Park 
151f23b8eeeSSeongJae Park static void damon_free_region(struct damon_region *r)
152f23b8eeeSSeongJae Park {
153a1870944SDawei Li 	kmem_cache_free(damon_region_cache, r);
154f23b8eeeSSeongJae Park }
155f23b8eeeSSeongJae Park 
156b9a6ac4eSSeongJae Park void damon_destroy_region(struct damon_region *r, struct damon_target *t)
157f23b8eeeSSeongJae Park {
158b9a6ac4eSSeongJae Park 	damon_del_region(r, t);
159f23b8eeeSSeongJae Park 	damon_free_region(r);
160f23b8eeeSSeongJae Park }
161f23b8eeeSSeongJae Park 
162d0723bc0SSeongJae Park /*
163d0723bc0SSeongJae Park  * Check whether a region is intersecting an address range
164d0723bc0SSeongJae Park  *
165d0723bc0SSeongJae Park  * Returns true if it is.
166d0723bc0SSeongJae Park  */
167d0723bc0SSeongJae Park static bool damon_intersect(struct damon_region *r,
168d0723bc0SSeongJae Park 		struct damon_addr_range *re)
169d0723bc0SSeongJae Park {
170d0723bc0SSeongJae Park 	return !(r->ar.end <= re->start || re->end <= r->ar.start);
171d0723bc0SSeongJae Park }
172d0723bc0SSeongJae Park 
173d0723bc0SSeongJae Park /*
1749c950c22SSeongJae Park  * Fill holes in regions with new regions.
1759c950c22SSeongJae Park  */
1769c950c22SSeongJae Park static int damon_fill_regions_holes(struct damon_region *first,
1779c950c22SSeongJae Park 		struct damon_region *last, struct damon_target *t)
1789c950c22SSeongJae Park {
1799c950c22SSeongJae Park 	struct damon_region *r = first;
1809c950c22SSeongJae Park 
1819c950c22SSeongJae Park 	damon_for_each_region_from(r, t) {
1829c950c22SSeongJae Park 		struct damon_region *next, *newr;
1839c950c22SSeongJae Park 
1849c950c22SSeongJae Park 		if (r == last)
1859c950c22SSeongJae Park 			break;
1869c950c22SSeongJae Park 		next = damon_next_region(r);
1879c950c22SSeongJae Park 		if (r->ar.end != next->ar.start) {
1889c950c22SSeongJae Park 			newr = damon_new_region(r->ar.end, next->ar.start);
1899c950c22SSeongJae Park 			if (!newr)
1909c950c22SSeongJae Park 				return -ENOMEM;
1919c950c22SSeongJae Park 			damon_insert_region(newr, r, next, t);
1929c950c22SSeongJae Park 		}
1939c950c22SSeongJae Park 	}
1949c950c22SSeongJae Park 	return 0;
1959c950c22SSeongJae Park }
1969c950c22SSeongJae Park 
1979c950c22SSeongJae Park /*
198d0723bc0SSeongJae Park  * damon_set_regions() - Set regions of a target for given address ranges.
199d0723bc0SSeongJae Park  * @t:		the given target.
200d0723bc0SSeongJae Park  * @ranges:	array of new monitoring target ranges.
201d0723bc0SSeongJae Park  * @nr_ranges:	length of @ranges.
202d0723bc0SSeongJae Park  *
203d0723bc0SSeongJae Park  * This function adds new regions to, or modify existing regions of a
204d0723bc0SSeongJae Park  * monitoring target to fit in specific ranges.
205d0723bc0SSeongJae Park  *
206d0723bc0SSeongJae Park  * Return: 0 if success, or negative error code otherwise.
207d0723bc0SSeongJae Park  */
208d0723bc0SSeongJae Park int damon_set_regions(struct damon_target *t, struct damon_addr_range *ranges,
209d0723bc0SSeongJae Park 		unsigned int nr_ranges)
210d0723bc0SSeongJae Park {
211d0723bc0SSeongJae Park 	struct damon_region *r, *next;
212d0723bc0SSeongJae Park 	unsigned int i;
2139c950c22SSeongJae Park 	int err;
214d0723bc0SSeongJae Park 
215d0723bc0SSeongJae Park 	/* Remove regions which are not in the new ranges */
216d0723bc0SSeongJae Park 	damon_for_each_region_safe(r, next, t) {
217d0723bc0SSeongJae Park 		for (i = 0; i < nr_ranges; i++) {
218d0723bc0SSeongJae Park 			if (damon_intersect(r, &ranges[i]))
219d0723bc0SSeongJae Park 				break;
220d0723bc0SSeongJae Park 		}
221d0723bc0SSeongJae Park 		if (i == nr_ranges)
222d0723bc0SSeongJae Park 			damon_destroy_region(r, t);
223d0723bc0SSeongJae Park 	}
224d0723bc0SSeongJae Park 
22536001cbaSKaixu Xia 	r = damon_first_region(t);
226d0723bc0SSeongJae Park 	/* Add new regions or resize existing regions to fit in the ranges */
227d0723bc0SSeongJae Park 	for (i = 0; i < nr_ranges; i++) {
228d0723bc0SSeongJae Park 		struct damon_region *first = NULL, *last, *newr;
229d0723bc0SSeongJae Park 		struct damon_addr_range *range;
230d0723bc0SSeongJae Park 
231d0723bc0SSeongJae Park 		range = &ranges[i];
232d0723bc0SSeongJae Park 		/* Get the first/last regions intersecting with the range */
23336001cbaSKaixu Xia 		damon_for_each_region_from(r, t) {
234d0723bc0SSeongJae Park 			if (damon_intersect(r, range)) {
235d0723bc0SSeongJae Park 				if (!first)
236d0723bc0SSeongJae Park 					first = r;
237d0723bc0SSeongJae Park 				last = r;
238d0723bc0SSeongJae Park 			}
239d0723bc0SSeongJae Park 			if (r->ar.start >= range->end)
240d0723bc0SSeongJae Park 				break;
241d0723bc0SSeongJae Park 		}
242d0723bc0SSeongJae Park 		if (!first) {
243d0723bc0SSeongJae Park 			/* no region intersects with this range */
244d0723bc0SSeongJae Park 			newr = damon_new_region(
245d0723bc0SSeongJae Park 					ALIGN_DOWN(range->start,
246d0723bc0SSeongJae Park 						DAMON_MIN_REGION),
247d0723bc0SSeongJae Park 					ALIGN(range->end, DAMON_MIN_REGION));
248d0723bc0SSeongJae Park 			if (!newr)
249d0723bc0SSeongJae Park 				return -ENOMEM;
250d0723bc0SSeongJae Park 			damon_insert_region(newr, damon_prev_region(r), r, t);
251d0723bc0SSeongJae Park 		} else {
252d0723bc0SSeongJae Park 			/* resize intersecting regions to fit in this range */
253d0723bc0SSeongJae Park 			first->ar.start = ALIGN_DOWN(range->start,
254d0723bc0SSeongJae Park 					DAMON_MIN_REGION);
255d0723bc0SSeongJae Park 			last->ar.end = ALIGN(range->end, DAMON_MIN_REGION);
2569c950c22SSeongJae Park 
2579c950c22SSeongJae Park 			/* fill possible holes in the range */
2589c950c22SSeongJae Park 			err = damon_fill_regions_holes(first, last, t);
2599c950c22SSeongJae Park 			if (err)
2609c950c22SSeongJae Park 				return err;
261d0723bc0SSeongJae Park 		}
262d0723bc0SSeongJae Park 	}
263d0723bc0SSeongJae Park 	return 0;
264d0723bc0SSeongJae Park }
265d0723bc0SSeongJae Park 
26698def236SSeongJae Park struct damos_filter *damos_new_filter(enum damos_filter_type type,
26798def236SSeongJae Park 		bool matching)
26898def236SSeongJae Park {
26998def236SSeongJae Park 	struct damos_filter *filter;
27098def236SSeongJae Park 
27198def236SSeongJae Park 	filter = kmalloc(sizeof(*filter), GFP_KERNEL);
27298def236SSeongJae Park 	if (!filter)
27398def236SSeongJae Park 		return NULL;
27498def236SSeongJae Park 	filter->type = type;
27598def236SSeongJae Park 	filter->matching = matching;
276*5f1fc67fSSeongJae Park 	INIT_LIST_HEAD(&filter->list);
27798def236SSeongJae Park 	return filter;
27898def236SSeongJae Park }
27998def236SSeongJae Park 
28098def236SSeongJae Park void damos_add_filter(struct damos *s, struct damos_filter *f)
28198def236SSeongJae Park {
28298def236SSeongJae Park 	list_add_tail(&f->list, &s->filters);
28398def236SSeongJae Park }
28498def236SSeongJae Park 
28598def236SSeongJae Park static void damos_del_filter(struct damos_filter *f)
28698def236SSeongJae Park {
28798def236SSeongJae Park 	list_del(&f->list);
28898def236SSeongJae Park }
28998def236SSeongJae Park 
29098def236SSeongJae Park static void damos_free_filter(struct damos_filter *f)
29198def236SSeongJae Park {
29298def236SSeongJae Park 	kfree(f);
29398def236SSeongJae Park }
29498def236SSeongJae Park 
29598def236SSeongJae Park void damos_destroy_filter(struct damos_filter *f)
29698def236SSeongJae Park {
29798def236SSeongJae Park 	damos_del_filter(f);
29898def236SSeongJae Park 	damos_free_filter(f);
29998def236SSeongJae Park }
30098def236SSeongJae Park 
30170e0c1d1SSeongJae Park /* initialize private fields of damos_quota and return the pointer */
30270e0c1d1SSeongJae Park static struct damos_quota *damos_quota_init_priv(struct damos_quota *quota)
30370e0c1d1SSeongJae Park {
30470e0c1d1SSeongJae Park 	quota->total_charged_sz = 0;
30570e0c1d1SSeongJae Park 	quota->total_charged_ns = 0;
30670e0c1d1SSeongJae Park 	quota->esz = 0;
30770e0c1d1SSeongJae Park 	quota->charged_sz = 0;
30870e0c1d1SSeongJae Park 	quota->charged_from = 0;
30970e0c1d1SSeongJae Park 	quota->charge_target_from = NULL;
31070e0c1d1SSeongJae Park 	quota->charge_addr_from = 0;
31170e0c1d1SSeongJae Park 	return quota;
31270e0c1d1SSeongJae Park }
31370e0c1d1SSeongJae Park 
314f5a79d7cSYajun Deng struct damos *damon_new_scheme(struct damos_access_pattern *pattern,
315ee801b7dSSeongJae Park 			enum damos_action action, struct damos_quota *quota,
316ee801b7dSSeongJae Park 			struct damos_watermarks *wmarks)
3171f366e42SSeongJae Park {
3181f366e42SSeongJae Park 	struct damos *scheme;
3191f366e42SSeongJae Park 
3201f366e42SSeongJae Park 	scheme = kmalloc(sizeof(*scheme), GFP_KERNEL);
3211f366e42SSeongJae Park 	if (!scheme)
3221f366e42SSeongJae Park 		return NULL;
32302f17037SSeongJae Park 	scheme->pattern = *pattern;
3241f366e42SSeongJae Park 	scheme->action = action;
32598def236SSeongJae Park 	INIT_LIST_HEAD(&scheme->filters);
3260e92c2eeSSeongJae Park 	scheme->stat = (struct damos_stat){};
3271f366e42SSeongJae Park 	INIT_LIST_HEAD(&scheme->list);
3281f366e42SSeongJae Park 
32970e0c1d1SSeongJae Park 	scheme->quota = *(damos_quota_init_priv(quota));
3302b8a248dSSeongJae Park 
33102f17037SSeongJae Park 	scheme->wmarks = *wmarks;
332ee801b7dSSeongJae Park 	scheme->wmarks.activated = true;
333ee801b7dSSeongJae Park 
3341f366e42SSeongJae Park 	return scheme;
3351f366e42SSeongJae Park }
3361f366e42SSeongJae Park 
3371f366e42SSeongJae Park void damon_add_scheme(struct damon_ctx *ctx, struct damos *s)
3381f366e42SSeongJae Park {
3391f366e42SSeongJae Park 	list_add_tail(&s->list, &ctx->schemes);
3401f366e42SSeongJae Park }
3411f366e42SSeongJae Park 
3421f366e42SSeongJae Park static void damon_del_scheme(struct damos *s)
3431f366e42SSeongJae Park {
3441f366e42SSeongJae Park 	list_del(&s->list);
3451f366e42SSeongJae Park }
3461f366e42SSeongJae Park 
3471f366e42SSeongJae Park static void damon_free_scheme(struct damos *s)
3481f366e42SSeongJae Park {
3491f366e42SSeongJae Park 	kfree(s);
3501f366e42SSeongJae Park }
3511f366e42SSeongJae Park 
3521f366e42SSeongJae Park void damon_destroy_scheme(struct damos *s)
3531f366e42SSeongJae Park {
35498def236SSeongJae Park 	struct damos_filter *f, *next;
35598def236SSeongJae Park 
35698def236SSeongJae Park 	damos_for_each_filter_safe(f, next, s)
35798def236SSeongJae Park 		damos_destroy_filter(f);
3581f366e42SSeongJae Park 	damon_del_scheme(s);
3591f366e42SSeongJae Park 	damon_free_scheme(s);
3601f366e42SSeongJae Park }
3611f366e42SSeongJae Park 
362f23b8eeeSSeongJae Park /*
363f23b8eeeSSeongJae Park  * Construct a damon_target struct
364f23b8eeeSSeongJae Park  *
365f23b8eeeSSeongJae Park  * Returns the pointer to the new struct if success, or NULL otherwise
366f23b8eeeSSeongJae Park  */
3671971bd63SSeongJae Park struct damon_target *damon_new_target(void)
368f23b8eeeSSeongJae Park {
369f23b8eeeSSeongJae Park 	struct damon_target *t;
370f23b8eeeSSeongJae Park 
371f23b8eeeSSeongJae Park 	t = kmalloc(sizeof(*t), GFP_KERNEL);
372f23b8eeeSSeongJae Park 	if (!t)
373f23b8eeeSSeongJae Park 		return NULL;
374f23b8eeeSSeongJae Park 
3751971bd63SSeongJae Park 	t->pid = NULL;
376b9a6ac4eSSeongJae Park 	t->nr_regions = 0;
377f23b8eeeSSeongJae Park 	INIT_LIST_HEAD(&t->regions_list);
378b1f44cdaSSeongJae Park 	INIT_LIST_HEAD(&t->list);
379f23b8eeeSSeongJae Park 
380f23b8eeeSSeongJae Park 	return t;
381f23b8eeeSSeongJae Park }
382f23b8eeeSSeongJae Park 
383f23b8eeeSSeongJae Park void damon_add_target(struct damon_ctx *ctx, struct damon_target *t)
384f23b8eeeSSeongJae Park {
385b9a6ac4eSSeongJae Park 	list_add_tail(&t->list, &ctx->adaptive_targets);
386f23b8eeeSSeongJae Park }
387f23b8eeeSSeongJae Park 
388b5ca3e83SXin Hao bool damon_targets_empty(struct damon_ctx *ctx)
389b5ca3e83SXin Hao {
390b5ca3e83SXin Hao 	return list_empty(&ctx->adaptive_targets);
391b5ca3e83SXin Hao }
392b5ca3e83SXin Hao 
393f23b8eeeSSeongJae Park static void damon_del_target(struct damon_target *t)
394f23b8eeeSSeongJae Park {
395f23b8eeeSSeongJae Park 	list_del(&t->list);
396f23b8eeeSSeongJae Park }
397f23b8eeeSSeongJae Park 
398f23b8eeeSSeongJae Park void damon_free_target(struct damon_target *t)
399f23b8eeeSSeongJae Park {
400f23b8eeeSSeongJae Park 	struct damon_region *r, *next;
401f23b8eeeSSeongJae Park 
402f23b8eeeSSeongJae Park 	damon_for_each_region_safe(r, next, t)
403f23b8eeeSSeongJae Park 		damon_free_region(r);
404f23b8eeeSSeongJae Park 	kfree(t);
405f23b8eeeSSeongJae Park }
406f23b8eeeSSeongJae Park 
407f23b8eeeSSeongJae Park void damon_destroy_target(struct damon_target *t)
408f23b8eeeSSeongJae Park {
409f23b8eeeSSeongJae Park 	damon_del_target(t);
410f23b8eeeSSeongJae Park 	damon_free_target(t);
411f23b8eeeSSeongJae Park }
412f23b8eeeSSeongJae Park 
413b9a6ac4eSSeongJae Park unsigned int damon_nr_regions(struct damon_target *t)
414b9a6ac4eSSeongJae Park {
415b9a6ac4eSSeongJae Park 	return t->nr_regions;
416b9a6ac4eSSeongJae Park }
417b9a6ac4eSSeongJae Park 
4182224d848SSeongJae Park struct damon_ctx *damon_new_ctx(void)
4192224d848SSeongJae Park {
4202224d848SSeongJae Park 	struct damon_ctx *ctx;
4212224d848SSeongJae Park 
4222224d848SSeongJae Park 	ctx = kzalloc(sizeof(*ctx), GFP_KERNEL);
4232224d848SSeongJae Park 	if (!ctx)
4242224d848SSeongJae Park 		return NULL;
4252224d848SSeongJae Park 
426cbeaa77bSSeongJae Park 	ctx->attrs.sample_interval = 5 * 1000;
427cbeaa77bSSeongJae Park 	ctx->attrs.aggr_interval = 100 * 1000;
428cbeaa77bSSeongJae Park 	ctx->attrs.ops_update_interval = 60 * 1000 * 1000;
4292224d848SSeongJae Park 
4302224d848SSeongJae Park 	ktime_get_coarse_ts64(&ctx->last_aggregation);
431f7d911c3SSeongJae Park 	ctx->last_ops_update = ctx->last_aggregation;
4322224d848SSeongJae Park 
4332224d848SSeongJae Park 	mutex_init(&ctx->kdamond_lock);
4342224d848SSeongJae Park 
435cbeaa77bSSeongJae Park 	ctx->attrs.min_nr_regions = 10;
436cbeaa77bSSeongJae Park 	ctx->attrs.max_nr_regions = 1000;
437b9a6ac4eSSeongJae Park 
438b9a6ac4eSSeongJae Park 	INIT_LIST_HEAD(&ctx->adaptive_targets);
4391f366e42SSeongJae Park 	INIT_LIST_HEAD(&ctx->schemes);
4402224d848SSeongJae Park 
4412224d848SSeongJae Park 	return ctx;
4422224d848SSeongJae Park }
4432224d848SSeongJae Park 
444f23b8eeeSSeongJae Park static void damon_destroy_targets(struct damon_ctx *ctx)
445f23b8eeeSSeongJae Park {
446f23b8eeeSSeongJae Park 	struct damon_target *t, *next_t;
447f23b8eeeSSeongJae Park 
448f7d911c3SSeongJae Park 	if (ctx->ops.cleanup) {
449f7d911c3SSeongJae Park 		ctx->ops.cleanup(ctx);
450f23b8eeeSSeongJae Park 		return;
451f23b8eeeSSeongJae Park 	}
452f23b8eeeSSeongJae Park 
453f23b8eeeSSeongJae Park 	damon_for_each_target_safe(t, next_t, ctx)
454f23b8eeeSSeongJae Park 		damon_destroy_target(t);
455f23b8eeeSSeongJae Park }
456f23b8eeeSSeongJae Park 
4572224d848SSeongJae Park void damon_destroy_ctx(struct damon_ctx *ctx)
4582224d848SSeongJae Park {
4591f366e42SSeongJae Park 	struct damos *s, *next_s;
4601f366e42SSeongJae Park 
461f23b8eeeSSeongJae Park 	damon_destroy_targets(ctx);
4621f366e42SSeongJae Park 
4631f366e42SSeongJae Park 	damon_for_each_scheme_safe(s, next_s, ctx)
4641f366e42SSeongJae Park 		damon_destroy_scheme(s);
4651f366e42SSeongJae Park 
4662224d848SSeongJae Park 	kfree(ctx);
4672224d848SSeongJae Park }
4682224d848SSeongJae Park 
4692f5bef5aSSeongJae Park static unsigned int damon_age_for_new_attrs(unsigned int age,
4702f5bef5aSSeongJae Park 		struct damon_attrs *old_attrs, struct damon_attrs *new_attrs)
4712f5bef5aSSeongJae Park {
4722f5bef5aSSeongJae Park 	return age * old_attrs->aggr_interval / new_attrs->aggr_interval;
4732f5bef5aSSeongJae Park }
4742f5bef5aSSeongJae Park 
4752f5bef5aSSeongJae Park /* convert access ratio in bp (per 10,000) to nr_accesses */
4762f5bef5aSSeongJae Park static unsigned int damon_accesses_bp_to_nr_accesses(
4772f5bef5aSSeongJae Park 		unsigned int accesses_bp, struct damon_attrs *attrs)
4782f5bef5aSSeongJae Park {
4792f5bef5aSSeongJae Park 	unsigned int max_nr_accesses =
4802f5bef5aSSeongJae Park 		attrs->aggr_interval / attrs->sample_interval;
4812f5bef5aSSeongJae Park 
4822f5bef5aSSeongJae Park 	return accesses_bp * max_nr_accesses / 10000;
4832f5bef5aSSeongJae Park }
4842f5bef5aSSeongJae Park 
4852f5bef5aSSeongJae Park /* convert nr_accesses to access ratio in bp (per 10,000) */
4862f5bef5aSSeongJae Park static unsigned int damon_nr_accesses_to_accesses_bp(
4872f5bef5aSSeongJae Park 		unsigned int nr_accesses, struct damon_attrs *attrs)
4882f5bef5aSSeongJae Park {
4892f5bef5aSSeongJae Park 	unsigned int max_nr_accesses =
4902f5bef5aSSeongJae Park 		attrs->aggr_interval / attrs->sample_interval;
4912f5bef5aSSeongJae Park 
4922f5bef5aSSeongJae Park 	return nr_accesses * 10000 / max_nr_accesses;
4932f5bef5aSSeongJae Park }
4942f5bef5aSSeongJae Park 
4952f5bef5aSSeongJae Park static unsigned int damon_nr_accesses_for_new_attrs(unsigned int nr_accesses,
4962f5bef5aSSeongJae Park 		struct damon_attrs *old_attrs, struct damon_attrs *new_attrs)
4972f5bef5aSSeongJae Park {
4982f5bef5aSSeongJae Park 	return damon_accesses_bp_to_nr_accesses(
4992f5bef5aSSeongJae Park 			damon_nr_accesses_to_accesses_bp(
5002f5bef5aSSeongJae Park 				nr_accesses, old_attrs),
5012f5bef5aSSeongJae Park 			new_attrs);
5022f5bef5aSSeongJae Park }
5032f5bef5aSSeongJae Park 
5042f5bef5aSSeongJae Park static void damon_update_monitoring_result(struct damon_region *r,
5052f5bef5aSSeongJae Park 		struct damon_attrs *old_attrs, struct damon_attrs *new_attrs)
5062f5bef5aSSeongJae Park {
5072f5bef5aSSeongJae Park 	r->nr_accesses = damon_nr_accesses_for_new_attrs(r->nr_accesses,
5082f5bef5aSSeongJae Park 			old_attrs, new_attrs);
5092f5bef5aSSeongJae Park 	r->age = damon_age_for_new_attrs(r->age, old_attrs, new_attrs);
5102f5bef5aSSeongJae Park }
5112f5bef5aSSeongJae Park 
5122f5bef5aSSeongJae Park /*
5132f5bef5aSSeongJae Park  * region->nr_accesses is the number of sampling intervals in the last
5142f5bef5aSSeongJae Park  * aggregation interval that access to the region has found, and region->age is
5152f5bef5aSSeongJae Park  * the number of aggregation intervals that its access pattern has maintained.
5162f5bef5aSSeongJae Park  * For the reason, the real meaning of the two fields depend on current
5172f5bef5aSSeongJae Park  * sampling interval and aggregation interval.  This function updates
5182f5bef5aSSeongJae Park  * ->nr_accesses and ->age of given damon_ctx's regions for new damon_attrs.
5192f5bef5aSSeongJae Park  */
5202f5bef5aSSeongJae Park static void damon_update_monitoring_results(struct damon_ctx *ctx,
5212f5bef5aSSeongJae Park 		struct damon_attrs *new_attrs)
5222f5bef5aSSeongJae Park {
5232f5bef5aSSeongJae Park 	struct damon_attrs *old_attrs = &ctx->attrs;
5242f5bef5aSSeongJae Park 	struct damon_target *t;
5252f5bef5aSSeongJae Park 	struct damon_region *r;
5262f5bef5aSSeongJae Park 
5272f5bef5aSSeongJae Park 	/* if any interval is zero, simply forgive conversion */
5282f5bef5aSSeongJae Park 	if (!old_attrs->sample_interval || !old_attrs->aggr_interval ||
5292f5bef5aSSeongJae Park 			!new_attrs->sample_interval ||
5302f5bef5aSSeongJae Park 			!new_attrs->aggr_interval)
5312f5bef5aSSeongJae Park 		return;
5322f5bef5aSSeongJae Park 
5332f5bef5aSSeongJae Park 	damon_for_each_target(t, ctx)
5342f5bef5aSSeongJae Park 		damon_for_each_region(r, t)
5352f5bef5aSSeongJae Park 			damon_update_monitoring_result(
5362f5bef5aSSeongJae Park 					r, old_attrs, new_attrs);
5372f5bef5aSSeongJae Park }
5382f5bef5aSSeongJae Park 
5392224d848SSeongJae Park /**
5402224d848SSeongJae Park  * damon_set_attrs() - Set attributes for the monitoring.
5412224d848SSeongJae Park  * @ctx:		monitoring context
542bead3b00SSeongJae Park  * @attrs:		monitoring attributes
5432224d848SSeongJae Park  *
5442224d848SSeongJae Park  * This function should not be called while the kdamond is running.
5452224d848SSeongJae Park  * Every time interval is in micro-seconds.
5462224d848SSeongJae Park  *
5472224d848SSeongJae Park  * Return: 0 on success, negative error code otherwise.
5482224d848SSeongJae Park  */
549bead3b00SSeongJae Park int damon_set_attrs(struct damon_ctx *ctx, struct damon_attrs *attrs)
5502224d848SSeongJae Park {
551bead3b00SSeongJae Park 	if (attrs->min_nr_regions < 3)
552b9a6ac4eSSeongJae Park 		return -EINVAL;
553bead3b00SSeongJae Park 	if (attrs->min_nr_regions > attrs->max_nr_regions)
554b9a6ac4eSSeongJae Park 		return -EINVAL;
5555ff6e2ffSKefeng Wang 	if (attrs->sample_interval > attrs->aggr_interval)
5565ff6e2ffSKefeng Wang 		return -EINVAL;
557b9a6ac4eSSeongJae Park 
5582f5bef5aSSeongJae Park 	damon_update_monitoring_results(ctx, attrs);
559bead3b00SSeongJae Park 	ctx->attrs = *attrs;
5602224d848SSeongJae Park 	return 0;
5612224d848SSeongJae Park }
5622224d848SSeongJae Park 
5634bc05954SSeongJae Park /**
5641f366e42SSeongJae Park  * damon_set_schemes() - Set data access monitoring based operation schemes.
5651f366e42SSeongJae Park  * @ctx:	monitoring context
5661f366e42SSeongJae Park  * @schemes:	array of the schemes
5671f366e42SSeongJae Park  * @nr_schemes:	number of entries in @schemes
5681f366e42SSeongJae Park  *
5691f366e42SSeongJae Park  * This function should not be called while the kdamond of the context is
5701f366e42SSeongJae Park  * running.
5711f366e42SSeongJae Park  */
572cc713520SKaixu Xia void damon_set_schemes(struct damon_ctx *ctx, struct damos **schemes,
5731f366e42SSeongJae Park 			ssize_t nr_schemes)
5741f366e42SSeongJae Park {
5751f366e42SSeongJae Park 	struct damos *s, *next;
5761f366e42SSeongJae Park 	ssize_t i;
5771f366e42SSeongJae Park 
5781f366e42SSeongJae Park 	damon_for_each_scheme_safe(s, next, ctx)
5791f366e42SSeongJae Park 		damon_destroy_scheme(s);
5801f366e42SSeongJae Park 	for (i = 0; i < nr_schemes; i++)
5811f366e42SSeongJae Park 		damon_add_scheme(ctx, schemes[i]);
5821f366e42SSeongJae Park }
5831f366e42SSeongJae Park 
5841f366e42SSeongJae Park /**
5854bc05954SSeongJae Park  * damon_nr_running_ctxs() - Return number of currently running contexts.
5864bc05954SSeongJae Park  */
5874bc05954SSeongJae Park int damon_nr_running_ctxs(void)
5884bc05954SSeongJae Park {
5894bc05954SSeongJae Park 	int nr_ctxs;
5904bc05954SSeongJae Park 
5914bc05954SSeongJae Park 	mutex_lock(&damon_lock);
5924bc05954SSeongJae Park 	nr_ctxs = nr_running_ctxs;
5934bc05954SSeongJae Park 	mutex_unlock(&damon_lock);
5944bc05954SSeongJae Park 
5954bc05954SSeongJae Park 	return nr_ctxs;
5964bc05954SSeongJae Park }
5974bc05954SSeongJae Park 
598b9a6ac4eSSeongJae Park /* Returns the size upper limit for each monitoring region */
599b9a6ac4eSSeongJae Park static unsigned long damon_region_sz_limit(struct damon_ctx *ctx)
600b9a6ac4eSSeongJae Park {
601b9a6ac4eSSeongJae Park 	struct damon_target *t;
602b9a6ac4eSSeongJae Park 	struct damon_region *r;
603b9a6ac4eSSeongJae Park 	unsigned long sz = 0;
604b9a6ac4eSSeongJae Park 
605b9a6ac4eSSeongJae Park 	damon_for_each_target(t, ctx) {
606b9a6ac4eSSeongJae Park 		damon_for_each_region(r, t)
607ab63f63fSXin Hao 			sz += damon_sz_region(r);
608b9a6ac4eSSeongJae Park 	}
609b9a6ac4eSSeongJae Park 
610cbeaa77bSSeongJae Park 	if (ctx->attrs.min_nr_regions)
611cbeaa77bSSeongJae Park 		sz /= ctx->attrs.min_nr_regions;
612b9a6ac4eSSeongJae Park 	if (sz < DAMON_MIN_REGION)
613b9a6ac4eSSeongJae Park 		sz = DAMON_MIN_REGION;
614b9a6ac4eSSeongJae Park 
615b9a6ac4eSSeongJae Park 	return sz;
616b9a6ac4eSSeongJae Park }
617b9a6ac4eSSeongJae Park 
6182224d848SSeongJae Park static int kdamond_fn(void *data);
6192224d848SSeongJae Park 
6202224d848SSeongJae Park /*
6212224d848SSeongJae Park  * __damon_start() - Starts monitoring with given context.
6222224d848SSeongJae Park  * @ctx:	monitoring context
6232224d848SSeongJae Park  *
6242224d848SSeongJae Park  * This function should be called while damon_lock is hold.
6252224d848SSeongJae Park  *
6262224d848SSeongJae Park  * Return: 0 on success, negative error code otherwise.
6272224d848SSeongJae Park  */
6282224d848SSeongJae Park static int __damon_start(struct damon_ctx *ctx)
6292224d848SSeongJae Park {
6302224d848SSeongJae Park 	int err = -EBUSY;
6312224d848SSeongJae Park 
6322224d848SSeongJae Park 	mutex_lock(&ctx->kdamond_lock);
6332224d848SSeongJae Park 	if (!ctx->kdamond) {
6342224d848SSeongJae Park 		err = 0;
6352224d848SSeongJae Park 		ctx->kdamond = kthread_run(kdamond_fn, ctx, "kdamond.%d",
6362224d848SSeongJae Park 				nr_running_ctxs);
6372224d848SSeongJae Park 		if (IS_ERR(ctx->kdamond)) {
6382224d848SSeongJae Park 			err = PTR_ERR(ctx->kdamond);
6397ec1992bSColin Ian King 			ctx->kdamond = NULL;
6402224d848SSeongJae Park 		}
6412224d848SSeongJae Park 	}
6422224d848SSeongJae Park 	mutex_unlock(&ctx->kdamond_lock);
6432224d848SSeongJae Park 
6442224d848SSeongJae Park 	return err;
6452224d848SSeongJae Park }
6462224d848SSeongJae Park 
6472224d848SSeongJae Park /**
6482224d848SSeongJae Park  * damon_start() - Starts the monitorings for a given group of contexts.
6492224d848SSeongJae Park  * @ctxs:	an array of the pointers for contexts to start monitoring
6502224d848SSeongJae Park  * @nr_ctxs:	size of @ctxs
6518b9b0d33SSeongJae Park  * @exclusive:	exclusiveness of this contexts group
6522224d848SSeongJae Park  *
6532224d848SSeongJae Park  * This function starts a group of monitoring threads for a group of monitoring
6542224d848SSeongJae Park  * contexts.  One thread per each context is created and run in parallel.  The
6558b9b0d33SSeongJae Park  * caller should handle synchronization between the threads by itself.  If
6568b9b0d33SSeongJae Park  * @exclusive is true and a group of threads that created by other
6578b9b0d33SSeongJae Park  * 'damon_start()' call is currently running, this function does nothing but
6588b9b0d33SSeongJae Park  * returns -EBUSY.
6592224d848SSeongJae Park  *
6602224d848SSeongJae Park  * Return: 0 on success, negative error code otherwise.
6612224d848SSeongJae Park  */
6628b9b0d33SSeongJae Park int damon_start(struct damon_ctx **ctxs, int nr_ctxs, bool exclusive)
6632224d848SSeongJae Park {
6642224d848SSeongJae Park 	int i;
6652224d848SSeongJae Park 	int err = 0;
6662224d848SSeongJae Park 
6672224d848SSeongJae Park 	mutex_lock(&damon_lock);
6688b9b0d33SSeongJae Park 	if ((exclusive && nr_running_ctxs) ||
6698b9b0d33SSeongJae Park 			(!exclusive && running_exclusive_ctxs)) {
6702224d848SSeongJae Park 		mutex_unlock(&damon_lock);
6712224d848SSeongJae Park 		return -EBUSY;
6722224d848SSeongJae Park 	}
6732224d848SSeongJae Park 
6742224d848SSeongJae Park 	for (i = 0; i < nr_ctxs; i++) {
6752224d848SSeongJae Park 		err = __damon_start(ctxs[i]);
6762224d848SSeongJae Park 		if (err)
6772224d848SSeongJae Park 			break;
6782224d848SSeongJae Park 		nr_running_ctxs++;
6792224d848SSeongJae Park 	}
6808b9b0d33SSeongJae Park 	if (exclusive && nr_running_ctxs)
6818b9b0d33SSeongJae Park 		running_exclusive_ctxs = true;
6822224d848SSeongJae Park 	mutex_unlock(&damon_lock);
6832224d848SSeongJae Park 
6842224d848SSeongJae Park 	return err;
6852224d848SSeongJae Park }
6862224d848SSeongJae Park 
6872224d848SSeongJae Park /*
6888b9b0d33SSeongJae Park  * __damon_stop() - Stops monitoring of a given context.
6892224d848SSeongJae Park  * @ctx:	monitoring context
6902224d848SSeongJae Park  *
6912224d848SSeongJae Park  * Return: 0 on success, negative error code otherwise.
6922224d848SSeongJae Park  */
6932224d848SSeongJae Park static int __damon_stop(struct damon_ctx *ctx)
6942224d848SSeongJae Park {
6950f91d133SChangbin Du 	struct task_struct *tsk;
6960f91d133SChangbin Du 
6972224d848SSeongJae Park 	mutex_lock(&ctx->kdamond_lock);
6980f91d133SChangbin Du 	tsk = ctx->kdamond;
6990f91d133SChangbin Du 	if (tsk) {
7000f91d133SChangbin Du 		get_task_struct(tsk);
7012224d848SSeongJae Park 		mutex_unlock(&ctx->kdamond_lock);
7020f91d133SChangbin Du 		kthread_stop(tsk);
7030f91d133SChangbin Du 		put_task_struct(tsk);
7042224d848SSeongJae Park 		return 0;
7052224d848SSeongJae Park 	}
7062224d848SSeongJae Park 	mutex_unlock(&ctx->kdamond_lock);
7072224d848SSeongJae Park 
7082224d848SSeongJae Park 	return -EPERM;
7092224d848SSeongJae Park }
7102224d848SSeongJae Park 
7112224d848SSeongJae Park /**
7122224d848SSeongJae Park  * damon_stop() - Stops the monitorings for a given group of contexts.
7132224d848SSeongJae Park  * @ctxs:	an array of the pointers for contexts to stop monitoring
7142224d848SSeongJae Park  * @nr_ctxs:	size of @ctxs
7152224d848SSeongJae Park  *
7162224d848SSeongJae Park  * Return: 0 on success, negative error code otherwise.
7172224d848SSeongJae Park  */
7182224d848SSeongJae Park int damon_stop(struct damon_ctx **ctxs, int nr_ctxs)
7192224d848SSeongJae Park {
7202224d848SSeongJae Park 	int i, err = 0;
7212224d848SSeongJae Park 
7222224d848SSeongJae Park 	for (i = 0; i < nr_ctxs; i++) {
7232224d848SSeongJae Park 		/* nr_running_ctxs is decremented in kdamond_fn */
7242224d848SSeongJae Park 		err = __damon_stop(ctxs[i]);
7252224d848SSeongJae Park 		if (err)
7268b9b0d33SSeongJae Park 			break;
7272224d848SSeongJae Park 	}
7282224d848SSeongJae Park 	return err;
7292224d848SSeongJae Park }
7302224d848SSeongJae Park 
7312224d848SSeongJae Park /*
7322224d848SSeongJae Park  * damon_check_reset_time_interval() - Check if a time interval is elapsed.
7332224d848SSeongJae Park  * @baseline:	the time to check whether the interval has elapsed since
7342224d848SSeongJae Park  * @interval:	the time interval (microseconds)
7352224d848SSeongJae Park  *
7362224d848SSeongJae Park  * See whether the given time interval has passed since the given baseline
7372224d848SSeongJae Park  * time.  If so, it also updates the baseline to current time for next check.
7382224d848SSeongJae Park  *
7392224d848SSeongJae Park  * Return:	true if the time interval has passed, or false otherwise.
7402224d848SSeongJae Park  */
7412224d848SSeongJae Park static bool damon_check_reset_time_interval(struct timespec64 *baseline,
7422224d848SSeongJae Park 		unsigned long interval)
7432224d848SSeongJae Park {
7442224d848SSeongJae Park 	struct timespec64 now;
7452224d848SSeongJae Park 
7462224d848SSeongJae Park 	ktime_get_coarse_ts64(&now);
7472224d848SSeongJae Park 	if ((timespec64_to_ns(&now) - timespec64_to_ns(baseline)) <
7482224d848SSeongJae Park 			interval * 1000)
7492224d848SSeongJae Park 		return false;
7502224d848SSeongJae Park 	*baseline = now;
7512224d848SSeongJae Park 	return true;
7522224d848SSeongJae Park }
7532224d848SSeongJae Park 
7542224d848SSeongJae Park /*
7552224d848SSeongJae Park  * Check whether it is time to flush the aggregated information
7562224d848SSeongJae Park  */
7572224d848SSeongJae Park static bool kdamond_aggregate_interval_passed(struct damon_ctx *ctx)
7582224d848SSeongJae Park {
7592224d848SSeongJae Park 	return damon_check_reset_time_interval(&ctx->last_aggregation,
760cbeaa77bSSeongJae Park 			ctx->attrs.aggr_interval);
7612224d848SSeongJae Park }
7622224d848SSeongJae Park 
7632224d848SSeongJae Park /*
764f23b8eeeSSeongJae Park  * Reset the aggregated monitoring results ('nr_accesses' of each region).
765f23b8eeeSSeongJae Park  */
766f23b8eeeSSeongJae Park static void kdamond_reset_aggregated(struct damon_ctx *c)
767f23b8eeeSSeongJae Park {
768f23b8eeeSSeongJae Park 	struct damon_target *t;
76976fd0285SSeongJae Park 	unsigned int ti = 0;	/* target's index */
770f23b8eeeSSeongJae Park 
771f23b8eeeSSeongJae Park 	damon_for_each_target(t, c) {
772f23b8eeeSSeongJae Park 		struct damon_region *r;
773f23b8eeeSSeongJae Park 
7742fcb9362SSeongJae Park 		damon_for_each_region(r, t) {
77576fd0285SSeongJae Park 			trace_damon_aggregated(t, ti, r, damon_nr_regions(t));
776fda504faSSeongJae Park 			r->last_nr_accesses = r->nr_accesses;
777f23b8eeeSSeongJae Park 			r->nr_accesses = 0;
778f23b8eeeSSeongJae Park 		}
77976fd0285SSeongJae Park 		ti++;
780f23b8eeeSSeongJae Park 	}
7812fcb9362SSeongJae Park }
782f23b8eeeSSeongJae Park 
7834ed98243SKaixu Xia static void damon_split_region_at(struct damon_target *t,
7844ed98243SKaixu Xia 				  struct damon_region *r, unsigned long sz_r);
7852b8a248dSSeongJae Park 
78638683e00SSeongJae Park static bool __damos_valid_target(struct damon_region *r, struct damos *s)
78738683e00SSeongJae Park {
78838683e00SSeongJae Park 	unsigned long sz;
78938683e00SSeongJae Park 
790ab63f63fSXin Hao 	sz = damon_sz_region(r);
791f5a79d7cSYajun Deng 	return s->pattern.min_sz_region <= sz &&
792f5a79d7cSYajun Deng 		sz <= s->pattern.max_sz_region &&
793f5a79d7cSYajun Deng 		s->pattern.min_nr_accesses <= r->nr_accesses &&
794f5a79d7cSYajun Deng 		r->nr_accesses <= s->pattern.max_nr_accesses &&
795f5a79d7cSYajun Deng 		s->pattern.min_age_region <= r->age &&
796f5a79d7cSYajun Deng 		r->age <= s->pattern.max_age_region;
79738683e00SSeongJae Park }
79838683e00SSeongJae Park 
79938683e00SSeongJae Park static bool damos_valid_target(struct damon_ctx *c, struct damon_target *t,
80038683e00SSeongJae Park 		struct damon_region *r, struct damos *s)
80138683e00SSeongJae Park {
80238683e00SSeongJae Park 	bool ret = __damos_valid_target(r, s);
80338683e00SSeongJae Park 
804f7d911c3SSeongJae Park 	if (!ret || !s->quota.esz || !c->ops.get_scheme_score)
80538683e00SSeongJae Park 		return ret;
80638683e00SSeongJae Park 
807f7d911c3SSeongJae Park 	return c->ops.get_scheme_score(c, t, r, s) >= s->quota.min_score;
80838683e00SSeongJae Park }
80938683e00SSeongJae Park 
8102ea34989SSeongJae Park /*
8112ea34989SSeongJae Park  * damos_skip_charged_region() - Check if the given region or starting part of
8122ea34989SSeongJae Park  * it is already charged for the DAMOS quota.
8132ea34989SSeongJae Park  * @t:	The target of the region.
8142ea34989SSeongJae Park  * @rp:	The pointer to the region.
8152ea34989SSeongJae Park  * @s:	The scheme to be applied.
8162ea34989SSeongJae Park  *
8172ea34989SSeongJae Park  * If a quota of a scheme has exceeded in a quota charge window, the scheme's
8182ea34989SSeongJae Park  * action would applied to only a part of the target access pattern fulfilling
8192ea34989SSeongJae Park  * regions.  To avoid applying the scheme action to only already applied
8202ea34989SSeongJae Park  * regions, DAMON skips applying the scheme action to the regions that charged
8212ea34989SSeongJae Park  * in the previous charge window.
8222ea34989SSeongJae Park  *
8232ea34989SSeongJae Park  * This function checks if a given region should be skipped or not for the
8242ea34989SSeongJae Park  * reason.  If only the starting part of the region has previously charged,
8252ea34989SSeongJae Park  * this function splits the region into two so that the second one covers the
8262ea34989SSeongJae Park  * area that not charged in the previous charge widnow and saves the second
8272ea34989SSeongJae Park  * region in *rp and returns false, so that the caller can apply DAMON action
8282ea34989SSeongJae Park  * to the second one.
8292ea34989SSeongJae Park  *
8302ea34989SSeongJae Park  * Return: true if the region should be entirely skipped, false otherwise.
8312ea34989SSeongJae Park  */
8322ea34989SSeongJae Park static bool damos_skip_charged_region(struct damon_target *t,
8332ea34989SSeongJae Park 		struct damon_region **rp, struct damos *s)
8342ea34989SSeongJae Park {
8352ea34989SSeongJae Park 	struct damon_region *r = *rp;
8362ea34989SSeongJae Park 	struct damos_quota *quota = &s->quota;
8372ea34989SSeongJae Park 	unsigned long sz_to_skip;
8382ea34989SSeongJae Park 
8392ea34989SSeongJae Park 	/* Skip previously charged regions */
8402ea34989SSeongJae Park 	if (quota->charge_target_from) {
8412ea34989SSeongJae Park 		if (t != quota->charge_target_from)
8422ea34989SSeongJae Park 			return true;
8432ea34989SSeongJae Park 		if (r == damon_last_region(t)) {
8442ea34989SSeongJae Park 			quota->charge_target_from = NULL;
8452ea34989SSeongJae Park 			quota->charge_addr_from = 0;
8462ea34989SSeongJae Park 			return true;
8472ea34989SSeongJae Park 		}
8482ea34989SSeongJae Park 		if (quota->charge_addr_from &&
8492ea34989SSeongJae Park 				r->ar.end <= quota->charge_addr_from)
8502ea34989SSeongJae Park 			return true;
8512ea34989SSeongJae Park 
8522ea34989SSeongJae Park 		if (quota->charge_addr_from && r->ar.start <
8532ea34989SSeongJae Park 				quota->charge_addr_from) {
8542ea34989SSeongJae Park 			sz_to_skip = ALIGN_DOWN(quota->charge_addr_from -
8552ea34989SSeongJae Park 					r->ar.start, DAMON_MIN_REGION);
8562ea34989SSeongJae Park 			if (!sz_to_skip) {
8572ea34989SSeongJae Park 				if (damon_sz_region(r) <= DAMON_MIN_REGION)
8582ea34989SSeongJae Park 					return true;
8592ea34989SSeongJae Park 				sz_to_skip = DAMON_MIN_REGION;
8602ea34989SSeongJae Park 			}
8612ea34989SSeongJae Park 			damon_split_region_at(t, r, sz_to_skip);
8622ea34989SSeongJae Park 			r = damon_next_region(r);
8632ea34989SSeongJae Park 			*rp = r;
8642ea34989SSeongJae Park 		}
8652ea34989SSeongJae Park 		quota->charge_target_from = NULL;
8662ea34989SSeongJae Park 		quota->charge_addr_from = 0;
8672ea34989SSeongJae Park 	}
8682ea34989SSeongJae Park 	return false;
8692ea34989SSeongJae Park }
8702ea34989SSeongJae Park 
871d1cbbf62SSeongJae Park static void damos_update_stat(struct damos *s,
872d1cbbf62SSeongJae Park 		unsigned long sz_tried, unsigned long sz_applied)
873d1cbbf62SSeongJae Park {
874d1cbbf62SSeongJae Park 	s->stat.nr_tried++;
875d1cbbf62SSeongJae Park 	s->stat.sz_tried += sz_tried;
876d1cbbf62SSeongJae Park 	if (sz_applied)
877d1cbbf62SSeongJae Park 		s->stat.nr_applied++;
878d1cbbf62SSeongJae Park 	s->stat.sz_applied += sz_applied;
879d1cbbf62SSeongJae Park }
880d1cbbf62SSeongJae Park 
881e63a30c5SSeongJae Park static void damos_apply_scheme(struct damon_ctx *c, struct damon_target *t,
882e63a30c5SSeongJae Park 		struct damon_region *r, struct damos *s)
8831f366e42SSeongJae Park {
8842b8a248dSSeongJae Park 	struct damos_quota *quota = &s->quota;
885e63a30c5SSeongJae Park 	unsigned long sz = damon_sz_region(r);
8861cd24303SSeongJae Park 	struct timespec64 begin, end;
8870e92c2eeSSeongJae Park 	unsigned long sz_applied = 0;
88844467bbbSSeongJae Park 	int err = 0;
8892b8a248dSSeongJae Park 
890f7d911c3SSeongJae Park 	if (c->ops.apply_scheme) {
891e63a30c5SSeongJae Park 		if (quota->esz && quota->charged_sz + sz > quota->esz) {
8921cd24303SSeongJae Park 			sz = ALIGN_DOWN(quota->esz - quota->charged_sz,
8932b8a248dSSeongJae Park 					DAMON_MIN_REGION);
8942b8a248dSSeongJae Park 			if (!sz)
8952b8a248dSSeongJae Park 				goto update_stat;
8964ed98243SKaixu Xia 			damon_split_region_at(t, r, sz);
8972b8a248dSSeongJae Park 		}
8981cd24303SSeongJae Park 		ktime_get_coarse_ts64(&begin);
89944467bbbSSeongJae Park 		if (c->callback.before_damos_apply)
90044467bbbSSeongJae Park 			err = c->callback.before_damos_apply(c, t, r, s);
90144467bbbSSeongJae Park 		if (!err)
902f7d911c3SSeongJae Park 			sz_applied = c->ops.apply_scheme(c, t, r, s);
9031cd24303SSeongJae Park 		ktime_get_coarse_ts64(&end);
9041cd24303SSeongJae Park 		quota->total_charged_ns += timespec64_to_ns(&end) -
9051cd24303SSeongJae Park 			timespec64_to_ns(&begin);
9062b8a248dSSeongJae Park 		quota->charged_sz += sz;
9071cd24303SSeongJae Park 		if (quota->esz && quota->charged_sz >= quota->esz) {
90850585192SSeongJae Park 			quota->charge_target_from = t;
90950585192SSeongJae Park 			quota->charge_addr_from = r->ar.end + 1;
91050585192SSeongJae Park 		}
9112b8a248dSSeongJae Park 	}
9122f0b548cSSeongJae Park 	if (s->action != DAMOS_STAT)
9131f366e42SSeongJae Park 		r->age = 0;
9142b8a248dSSeongJae Park 
9152b8a248dSSeongJae Park update_stat:
916d1cbbf62SSeongJae Park 	damos_update_stat(s, sz, sz_applied);
9171f366e42SSeongJae Park }
918e63a30c5SSeongJae Park 
919e63a30c5SSeongJae Park static void damon_do_apply_schemes(struct damon_ctx *c,
920e63a30c5SSeongJae Park 				   struct damon_target *t,
921e63a30c5SSeongJae Park 				   struct damon_region *r)
922e63a30c5SSeongJae Park {
923e63a30c5SSeongJae Park 	struct damos *s;
924e63a30c5SSeongJae Park 
925e63a30c5SSeongJae Park 	damon_for_each_scheme(s, c) {
926e63a30c5SSeongJae Park 		struct damos_quota *quota = &s->quota;
927e63a30c5SSeongJae Park 
928e63a30c5SSeongJae Park 		if (!s->wmarks.activated)
929e63a30c5SSeongJae Park 			continue;
930e63a30c5SSeongJae Park 
931e63a30c5SSeongJae Park 		/* Check the quota */
932e63a30c5SSeongJae Park 		if (quota->esz && quota->charged_sz >= quota->esz)
933e63a30c5SSeongJae Park 			continue;
934e63a30c5SSeongJae Park 
935e63a30c5SSeongJae Park 		if (damos_skip_charged_region(t, &r, s))
936e63a30c5SSeongJae Park 			continue;
937e63a30c5SSeongJae Park 
938e63a30c5SSeongJae Park 		if (!damos_valid_target(c, t, r, s))
939e63a30c5SSeongJae Park 			continue;
940e63a30c5SSeongJae Park 
941e63a30c5SSeongJae Park 		damos_apply_scheme(c, t, r, s);
942e63a30c5SSeongJae Park 	}
9431f366e42SSeongJae Park }
9441f366e42SSeongJae Park 
9451cd24303SSeongJae Park /* Shouldn't be called if quota->ms and quota->sz are zero */
9461cd24303SSeongJae Park static void damos_set_effective_quota(struct damos_quota *quota)
9471cd24303SSeongJae Park {
9481cd24303SSeongJae Park 	unsigned long throughput;
9491cd24303SSeongJae Park 	unsigned long esz;
9501cd24303SSeongJae Park 
9511cd24303SSeongJae Park 	if (!quota->ms) {
9521cd24303SSeongJae Park 		quota->esz = quota->sz;
9531cd24303SSeongJae Park 		return;
9541cd24303SSeongJae Park 	}
9551cd24303SSeongJae Park 
9561cd24303SSeongJae Park 	if (quota->total_charged_ns)
9571cd24303SSeongJae Park 		throughput = quota->total_charged_sz * 1000000 /
9581cd24303SSeongJae Park 			quota->total_charged_ns;
9591cd24303SSeongJae Park 	else
9601cd24303SSeongJae Park 		throughput = PAGE_SIZE * 1024;
9611cd24303SSeongJae Park 	esz = throughput * quota->ms;
9621cd24303SSeongJae Park 
9631cd24303SSeongJae Park 	if (quota->sz && quota->sz < esz)
9641cd24303SSeongJae Park 		esz = quota->sz;
9651cd24303SSeongJae Park 	quota->esz = esz;
9661cd24303SSeongJae Park }
9671cd24303SSeongJae Park 
968898810e5SSeongJae Park static void damos_adjust_quota(struct damon_ctx *c, struct damos *s)
9691f366e42SSeongJae Park {
9702b8a248dSSeongJae Park 	struct damos_quota *quota = &s->quota;
971898810e5SSeongJae Park 	struct damon_target *t;
972898810e5SSeongJae Park 	struct damon_region *r;
97338683e00SSeongJae Park 	unsigned long cumulated_sz;
97438683e00SSeongJae Park 	unsigned int score, max_score = 0;
9752b8a248dSSeongJae Park 
9761cd24303SSeongJae Park 	if (!quota->ms && !quota->sz)
977898810e5SSeongJae Park 		return;
9782b8a248dSSeongJae Park 
9792b8a248dSSeongJae Park 	/* New charge window starts */
9802b8a248dSSeongJae Park 	if (time_after_eq(jiffies, quota->charged_from +
981898810e5SSeongJae Park 				msecs_to_jiffies(quota->reset_interval))) {
9826268eac3SSeongJae Park 		if (quota->esz && quota->charged_sz >= quota->esz)
9836268eac3SSeongJae Park 			s->stat.qt_exceeds++;
9841cd24303SSeongJae Park 		quota->total_charged_sz += quota->charged_sz;
9852b8a248dSSeongJae Park 		quota->charged_from = jiffies;
9862b8a248dSSeongJae Park 		quota->charged_sz = 0;
9871cd24303SSeongJae Park 		damos_set_effective_quota(quota);
9882b8a248dSSeongJae Park 	}
98938683e00SSeongJae Park 
990f7d911c3SSeongJae Park 	if (!c->ops.get_scheme_score)
991898810e5SSeongJae Park 		return;
99238683e00SSeongJae Park 
99338683e00SSeongJae Park 	/* Fill up the score histogram */
99438683e00SSeongJae Park 	memset(quota->histogram, 0, sizeof(quota->histogram));
99538683e00SSeongJae Park 	damon_for_each_target(t, c) {
99638683e00SSeongJae Park 		damon_for_each_region(r, t) {
99738683e00SSeongJae Park 			if (!__damos_valid_target(r, s))
99838683e00SSeongJae Park 				continue;
999898810e5SSeongJae Park 			score = c->ops.get_scheme_score(c, t, r, s);
1000ab63f63fSXin Hao 			quota->histogram[score] += damon_sz_region(r);
100138683e00SSeongJae Park 			if (score > max_score)
100238683e00SSeongJae Park 				max_score = score;
100338683e00SSeongJae Park 		}
100438683e00SSeongJae Park 	}
100538683e00SSeongJae Park 
100638683e00SSeongJae Park 	/* Set the min score limit */
100738683e00SSeongJae Park 	for (cumulated_sz = 0, score = max_score; ; score--) {
100838683e00SSeongJae Park 		cumulated_sz += quota->histogram[score];
100938683e00SSeongJae Park 		if (cumulated_sz >= quota->esz || !score)
101038683e00SSeongJae Park 			break;
101138683e00SSeongJae Park 	}
101238683e00SSeongJae Park 	quota->min_score = score;
10132b8a248dSSeongJae Park }
10141f366e42SSeongJae Park 
1015898810e5SSeongJae Park static void kdamond_apply_schemes(struct damon_ctx *c)
1016898810e5SSeongJae Park {
1017898810e5SSeongJae Park 	struct damon_target *t;
1018898810e5SSeongJae Park 	struct damon_region *r, *next_r;
1019898810e5SSeongJae Park 	struct damos *s;
1020898810e5SSeongJae Park 
1021898810e5SSeongJae Park 	damon_for_each_scheme(s, c) {
1022898810e5SSeongJae Park 		if (!s->wmarks.activated)
1023898810e5SSeongJae Park 			continue;
1024898810e5SSeongJae Park 
1025898810e5SSeongJae Park 		damos_adjust_quota(c, s);
1026898810e5SSeongJae Park 	}
1027898810e5SSeongJae Park 
10281f366e42SSeongJae Park 	damon_for_each_target(t, c) {
10292b8a248dSSeongJae Park 		damon_for_each_region_safe(r, next_r, t)
10301f366e42SSeongJae Park 			damon_do_apply_schemes(c, t, r);
10311f366e42SSeongJae Park 	}
10321f366e42SSeongJae Park }
10331f366e42SSeongJae Park 
1034b9a6ac4eSSeongJae Park /*
1035b9a6ac4eSSeongJae Park  * Merge two adjacent regions into one region
1036b9a6ac4eSSeongJae Park  */
1037b9a6ac4eSSeongJae Park static void damon_merge_two_regions(struct damon_target *t,
1038b9a6ac4eSSeongJae Park 		struct damon_region *l, struct damon_region *r)
1039b9a6ac4eSSeongJae Park {
1040652e0446SXin Hao 	unsigned long sz_l = damon_sz_region(l), sz_r = damon_sz_region(r);
1041b9a6ac4eSSeongJae Park 
1042b9a6ac4eSSeongJae Park 	l->nr_accesses = (l->nr_accesses * sz_l + r->nr_accesses * sz_r) /
1043b9a6ac4eSSeongJae Park 			(sz_l + sz_r);
1044fda504faSSeongJae Park 	l->age = (l->age * sz_l + r->age * sz_r) / (sz_l + sz_r);
1045b9a6ac4eSSeongJae Park 	l->ar.end = r->ar.end;
1046b9a6ac4eSSeongJae Park 	damon_destroy_region(r, t);
1047b9a6ac4eSSeongJae Park }
1048b9a6ac4eSSeongJae Park 
1049b9a6ac4eSSeongJae Park /*
1050b9a6ac4eSSeongJae Park  * Merge adjacent regions having similar access frequencies
1051b9a6ac4eSSeongJae Park  *
1052b9a6ac4eSSeongJae Park  * t		target affected by this merge operation
1053b9a6ac4eSSeongJae Park  * thres	'->nr_accesses' diff threshold for the merge
1054b9a6ac4eSSeongJae Park  * sz_limit	size upper limit of each region
1055b9a6ac4eSSeongJae Park  */
1056b9a6ac4eSSeongJae Park static void damon_merge_regions_of(struct damon_target *t, unsigned int thres,
1057b9a6ac4eSSeongJae Park 				   unsigned long sz_limit)
1058b9a6ac4eSSeongJae Park {
1059b9a6ac4eSSeongJae Park 	struct damon_region *r, *prev = NULL, *next;
1060b9a6ac4eSSeongJae Park 
1061b9a6ac4eSSeongJae Park 	damon_for_each_region_safe(r, next, t) {
1062d720bbbdSXin Hao 		if (abs(r->nr_accesses - r->last_nr_accesses) > thres)
1063fda504faSSeongJae Park 			r->age = 0;
1064fda504faSSeongJae Park 		else
1065fda504faSSeongJae Park 			r->age++;
1066fda504faSSeongJae Park 
1067b9a6ac4eSSeongJae Park 		if (prev && prev->ar.end == r->ar.start &&
1068d720bbbdSXin Hao 		    abs(prev->nr_accesses - r->nr_accesses) <= thres &&
1069652e0446SXin Hao 		    damon_sz_region(prev) + damon_sz_region(r) <= sz_limit)
1070b9a6ac4eSSeongJae Park 			damon_merge_two_regions(t, prev, r);
1071b9a6ac4eSSeongJae Park 		else
1072b9a6ac4eSSeongJae Park 			prev = r;
1073b9a6ac4eSSeongJae Park 	}
1074b9a6ac4eSSeongJae Park }
1075b9a6ac4eSSeongJae Park 
1076b9a6ac4eSSeongJae Park /*
1077b9a6ac4eSSeongJae Park  * Merge adjacent regions having similar access frequencies
1078b9a6ac4eSSeongJae Park  *
1079b9a6ac4eSSeongJae Park  * threshold	'->nr_accesses' diff threshold for the merge
1080b9a6ac4eSSeongJae Park  * sz_limit	size upper limit of each region
1081b9a6ac4eSSeongJae Park  *
1082b9a6ac4eSSeongJae Park  * This function merges monitoring target regions which are adjacent and their
1083b9a6ac4eSSeongJae Park  * access frequencies are similar.  This is for minimizing the monitoring
1084b9a6ac4eSSeongJae Park  * overhead under the dynamically changeable access pattern.  If a merge was
1085b9a6ac4eSSeongJae Park  * unnecessarily made, later 'kdamond_split_regions()' will revert it.
1086b9a6ac4eSSeongJae Park  */
1087b9a6ac4eSSeongJae Park static void kdamond_merge_regions(struct damon_ctx *c, unsigned int threshold,
1088b9a6ac4eSSeongJae Park 				  unsigned long sz_limit)
1089b9a6ac4eSSeongJae Park {
1090b9a6ac4eSSeongJae Park 	struct damon_target *t;
1091b9a6ac4eSSeongJae Park 
1092b9a6ac4eSSeongJae Park 	damon_for_each_target(t, c)
1093b9a6ac4eSSeongJae Park 		damon_merge_regions_of(t, threshold, sz_limit);
1094b9a6ac4eSSeongJae Park }
1095b9a6ac4eSSeongJae Park 
1096b9a6ac4eSSeongJae Park /*
1097b9a6ac4eSSeongJae Park  * Split a region in two
1098b9a6ac4eSSeongJae Park  *
1099b9a6ac4eSSeongJae Park  * r		the region to be split
1100b9a6ac4eSSeongJae Park  * sz_r		size of the first sub-region that will be made
1101b9a6ac4eSSeongJae Park  */
11024ed98243SKaixu Xia static void damon_split_region_at(struct damon_target *t,
11034ed98243SKaixu Xia 				  struct damon_region *r, unsigned long sz_r)
1104b9a6ac4eSSeongJae Park {
1105b9a6ac4eSSeongJae Park 	struct damon_region *new;
1106b9a6ac4eSSeongJae Park 
1107b9a6ac4eSSeongJae Park 	new = damon_new_region(r->ar.start + sz_r, r->ar.end);
1108b9a6ac4eSSeongJae Park 	if (!new)
1109b9a6ac4eSSeongJae Park 		return;
1110b9a6ac4eSSeongJae Park 
1111b9a6ac4eSSeongJae Park 	r->ar.end = new->ar.start;
1112b9a6ac4eSSeongJae Park 
1113fda504faSSeongJae Park 	new->age = r->age;
1114fda504faSSeongJae Park 	new->last_nr_accesses = r->last_nr_accesses;
1115fda504faSSeongJae Park 
1116b9a6ac4eSSeongJae Park 	damon_insert_region(new, r, damon_next_region(r), t);
1117b9a6ac4eSSeongJae Park }
1118b9a6ac4eSSeongJae Park 
1119b9a6ac4eSSeongJae Park /* Split every region in the given target into 'nr_subs' regions */
11204ed98243SKaixu Xia static void damon_split_regions_of(struct damon_target *t, int nr_subs)
1121b9a6ac4eSSeongJae Park {
1122b9a6ac4eSSeongJae Park 	struct damon_region *r, *next;
1123b9a6ac4eSSeongJae Park 	unsigned long sz_region, sz_sub = 0;
1124b9a6ac4eSSeongJae Park 	int i;
1125b9a6ac4eSSeongJae Park 
1126b9a6ac4eSSeongJae Park 	damon_for_each_region_safe(r, next, t) {
1127ab63f63fSXin Hao 		sz_region = damon_sz_region(r);
1128b9a6ac4eSSeongJae Park 
1129b9a6ac4eSSeongJae Park 		for (i = 0; i < nr_subs - 1 &&
1130b9a6ac4eSSeongJae Park 				sz_region > 2 * DAMON_MIN_REGION; i++) {
1131b9a6ac4eSSeongJae Park 			/*
1132b9a6ac4eSSeongJae Park 			 * Randomly select size of left sub-region to be at
1133b9a6ac4eSSeongJae Park 			 * least 10 percent and at most 90% of original region
1134b9a6ac4eSSeongJae Park 			 */
1135b9a6ac4eSSeongJae Park 			sz_sub = ALIGN_DOWN(damon_rand(1, 10) *
1136b9a6ac4eSSeongJae Park 					sz_region / 10, DAMON_MIN_REGION);
1137b9a6ac4eSSeongJae Park 			/* Do not allow blank region */
1138b9a6ac4eSSeongJae Park 			if (sz_sub == 0 || sz_sub >= sz_region)
1139b9a6ac4eSSeongJae Park 				continue;
1140b9a6ac4eSSeongJae Park 
11414ed98243SKaixu Xia 			damon_split_region_at(t, r, sz_sub);
1142b9a6ac4eSSeongJae Park 			sz_region = sz_sub;
1143b9a6ac4eSSeongJae Park 		}
1144b9a6ac4eSSeongJae Park 	}
1145b9a6ac4eSSeongJae Park }
1146b9a6ac4eSSeongJae Park 
1147b9a6ac4eSSeongJae Park /*
1148b9a6ac4eSSeongJae Park  * Split every target region into randomly-sized small regions
1149b9a6ac4eSSeongJae Park  *
1150b9a6ac4eSSeongJae Park  * This function splits every target region into random-sized small regions if
1151b9a6ac4eSSeongJae Park  * current total number of the regions is equal or smaller than half of the
1152b9a6ac4eSSeongJae Park  * user-specified maximum number of regions.  This is for maximizing the
1153b9a6ac4eSSeongJae Park  * monitoring accuracy under the dynamically changeable access patterns.  If a
1154b9a6ac4eSSeongJae Park  * split was unnecessarily made, later 'kdamond_merge_regions()' will revert
1155b9a6ac4eSSeongJae Park  * it.
1156b9a6ac4eSSeongJae Park  */
1157b9a6ac4eSSeongJae Park static void kdamond_split_regions(struct damon_ctx *ctx)
1158b9a6ac4eSSeongJae Park {
1159b9a6ac4eSSeongJae Park 	struct damon_target *t;
1160b9a6ac4eSSeongJae Park 	unsigned int nr_regions = 0;
1161b9a6ac4eSSeongJae Park 	static unsigned int last_nr_regions;
1162b9a6ac4eSSeongJae Park 	int nr_subregions = 2;
1163b9a6ac4eSSeongJae Park 
1164b9a6ac4eSSeongJae Park 	damon_for_each_target(t, ctx)
1165b9a6ac4eSSeongJae Park 		nr_regions += damon_nr_regions(t);
1166b9a6ac4eSSeongJae Park 
1167cbeaa77bSSeongJae Park 	if (nr_regions > ctx->attrs.max_nr_regions / 2)
1168b9a6ac4eSSeongJae Park 		return;
1169b9a6ac4eSSeongJae Park 
1170b9a6ac4eSSeongJae Park 	/* Maybe the middle of the region has different access frequency */
1171b9a6ac4eSSeongJae Park 	if (last_nr_regions == nr_regions &&
1172cbeaa77bSSeongJae Park 			nr_regions < ctx->attrs.max_nr_regions / 3)
1173b9a6ac4eSSeongJae Park 		nr_subregions = 3;
1174b9a6ac4eSSeongJae Park 
1175b9a6ac4eSSeongJae Park 	damon_for_each_target(t, ctx)
11764ed98243SKaixu Xia 		damon_split_regions_of(t, nr_subregions);
1177b9a6ac4eSSeongJae Park 
1178b9a6ac4eSSeongJae Park 	last_nr_regions = nr_regions;
1179b9a6ac4eSSeongJae Park }
1180b9a6ac4eSSeongJae Park 
1181f23b8eeeSSeongJae Park /*
1182f7d911c3SSeongJae Park  * Check whether it is time to check and apply the operations-related data
1183f7d911c3SSeongJae Park  * structures.
11842224d848SSeongJae Park  *
11852224d848SSeongJae Park  * Returns true if it is.
11862224d848SSeongJae Park  */
1187f7d911c3SSeongJae Park static bool kdamond_need_update_operations(struct damon_ctx *ctx)
11882224d848SSeongJae Park {
1189f7d911c3SSeongJae Park 	return damon_check_reset_time_interval(&ctx->last_ops_update,
1190cbeaa77bSSeongJae Park 			ctx->attrs.ops_update_interval);
11912224d848SSeongJae Park }
11922224d848SSeongJae Park 
11932224d848SSeongJae Park /*
11942224d848SSeongJae Park  * Check whether current monitoring should be stopped
11952224d848SSeongJae Park  *
11962224d848SSeongJae Park  * The monitoring is stopped when either the user requested to stop, or all
11972224d848SSeongJae Park  * monitoring targets are invalid.
11982224d848SSeongJae Park  *
11992224d848SSeongJae Park  * Returns true if need to stop current monitoring.
12002224d848SSeongJae Park  */
12012224d848SSeongJae Park static bool kdamond_need_stop(struct damon_ctx *ctx)
12022224d848SSeongJae Park {
1203f23b8eeeSSeongJae Park 	struct damon_target *t;
12042224d848SSeongJae Park 
12050f91d133SChangbin Du 	if (kthread_should_stop())
12062224d848SSeongJae Park 		return true;
12072224d848SSeongJae Park 
1208f7d911c3SSeongJae Park 	if (!ctx->ops.target_valid)
12092224d848SSeongJae Park 		return false;
12102224d848SSeongJae Park 
1211f23b8eeeSSeongJae Park 	damon_for_each_target(t, ctx) {
1212f7d911c3SSeongJae Park 		if (ctx->ops.target_valid(t))
1213f23b8eeeSSeongJae Park 			return false;
1214f23b8eeeSSeongJae Park 	}
1215f23b8eeeSSeongJae Park 
1216f23b8eeeSSeongJae Park 	return true;
12172224d848SSeongJae Park }
12182224d848SSeongJae Park 
1219ee801b7dSSeongJae Park static unsigned long damos_wmark_metric_value(enum damos_wmark_metric metric)
1220ee801b7dSSeongJae Park {
1221ee801b7dSSeongJae Park 	struct sysinfo i;
1222ee801b7dSSeongJae Park 
1223ee801b7dSSeongJae Park 	switch (metric) {
1224ee801b7dSSeongJae Park 	case DAMOS_WMARK_FREE_MEM_RATE:
1225ee801b7dSSeongJae Park 		si_meminfo(&i);
1226ee801b7dSSeongJae Park 		return i.freeram * 1000 / i.totalram;
1227ee801b7dSSeongJae Park 	default:
1228ee801b7dSSeongJae Park 		break;
1229ee801b7dSSeongJae Park 	}
1230ee801b7dSSeongJae Park 	return -EINVAL;
1231ee801b7dSSeongJae Park }
1232ee801b7dSSeongJae Park 
1233ee801b7dSSeongJae Park /*
1234ee801b7dSSeongJae Park  * Returns zero if the scheme is active.  Else, returns time to wait for next
1235ee801b7dSSeongJae Park  * watermark check in micro-seconds.
1236ee801b7dSSeongJae Park  */
1237ee801b7dSSeongJae Park static unsigned long damos_wmark_wait_us(struct damos *scheme)
1238ee801b7dSSeongJae Park {
1239ee801b7dSSeongJae Park 	unsigned long metric;
1240ee801b7dSSeongJae Park 
1241ee801b7dSSeongJae Park 	if (scheme->wmarks.metric == DAMOS_WMARK_NONE)
1242ee801b7dSSeongJae Park 		return 0;
1243ee801b7dSSeongJae Park 
1244ee801b7dSSeongJae Park 	metric = damos_wmark_metric_value(scheme->wmarks.metric);
1245ee801b7dSSeongJae Park 	/* higher than high watermark or lower than low watermark */
1246ee801b7dSSeongJae Park 	if (metric > scheme->wmarks.high || scheme->wmarks.low > metric) {
1247ee801b7dSSeongJae Park 		if (scheme->wmarks.activated)
124801078655SColin Ian King 			pr_debug("deactivate a scheme (%d) for %s wmark\n",
1249ee801b7dSSeongJae Park 					scheme->action,
1250ee801b7dSSeongJae Park 					metric > scheme->wmarks.high ?
1251ee801b7dSSeongJae Park 					"high" : "low");
1252ee801b7dSSeongJae Park 		scheme->wmarks.activated = false;
1253ee801b7dSSeongJae Park 		return scheme->wmarks.interval;
1254ee801b7dSSeongJae Park 	}
1255ee801b7dSSeongJae Park 
1256ee801b7dSSeongJae Park 	/* inactive and higher than middle watermark */
1257ee801b7dSSeongJae Park 	if ((scheme->wmarks.high >= metric && metric >= scheme->wmarks.mid) &&
1258ee801b7dSSeongJae Park 			!scheme->wmarks.activated)
1259ee801b7dSSeongJae Park 		return scheme->wmarks.interval;
1260ee801b7dSSeongJae Park 
1261ee801b7dSSeongJae Park 	if (!scheme->wmarks.activated)
1262ee801b7dSSeongJae Park 		pr_debug("activate a scheme (%d)\n", scheme->action);
1263ee801b7dSSeongJae Park 	scheme->wmarks.activated = true;
1264ee801b7dSSeongJae Park 	return 0;
1265ee801b7dSSeongJae Park }
1266ee801b7dSSeongJae Park 
1267ee801b7dSSeongJae Park static void kdamond_usleep(unsigned long usecs)
1268ee801b7dSSeongJae Park {
12694de46a30SSeongJae Park 	/* See Documentation/timers/timers-howto.rst for the thresholds */
12704de46a30SSeongJae Park 	if (usecs > 20 * USEC_PER_MSEC)
127170e92748SSeongJae Park 		schedule_timeout_idle(usecs_to_jiffies(usecs));
1272ee801b7dSSeongJae Park 	else
127370e92748SSeongJae Park 		usleep_idle_range(usecs, usecs + 1);
1274ee801b7dSSeongJae Park }
1275ee801b7dSSeongJae Park 
1276ee801b7dSSeongJae Park /* Returns negative error code if it's not activated but should return */
1277ee801b7dSSeongJae Park static int kdamond_wait_activation(struct damon_ctx *ctx)
1278ee801b7dSSeongJae Park {
1279ee801b7dSSeongJae Park 	struct damos *s;
1280ee801b7dSSeongJae Park 	unsigned long wait_time;
1281ee801b7dSSeongJae Park 	unsigned long min_wait_time = 0;
128278049e94SJonghyeon Kim 	bool init_wait_time = false;
1283ee801b7dSSeongJae Park 
1284ee801b7dSSeongJae Park 	while (!kdamond_need_stop(ctx)) {
1285ee801b7dSSeongJae Park 		damon_for_each_scheme(s, ctx) {
1286ee801b7dSSeongJae Park 			wait_time = damos_wmark_wait_us(s);
128778049e94SJonghyeon Kim 			if (!init_wait_time || wait_time < min_wait_time) {
128878049e94SJonghyeon Kim 				init_wait_time = true;
1289ee801b7dSSeongJae Park 				min_wait_time = wait_time;
1290ee801b7dSSeongJae Park 			}
129178049e94SJonghyeon Kim 		}
1292ee801b7dSSeongJae Park 		if (!min_wait_time)
1293ee801b7dSSeongJae Park 			return 0;
1294ee801b7dSSeongJae Park 
1295ee801b7dSSeongJae Park 		kdamond_usleep(min_wait_time);
12966e74d2bfSSeongJae Park 
12976e74d2bfSSeongJae Park 		if (ctx->callback.after_wmarks_check &&
12986e74d2bfSSeongJae Park 				ctx->callback.after_wmarks_check(ctx))
12996e74d2bfSSeongJae Park 			break;
1300ee801b7dSSeongJae Park 	}
1301ee801b7dSSeongJae Park 	return -EBUSY;
1302ee801b7dSSeongJae Park }
1303ee801b7dSSeongJae Park 
13042224d848SSeongJae Park /*
13052224d848SSeongJae Park  * The monitoring daemon that runs as a kernel thread
13062224d848SSeongJae Park  */
13072224d848SSeongJae Park static int kdamond_fn(void *data)
13082224d848SSeongJae Park {
1309cef4493fSYu Zhe 	struct damon_ctx *ctx = data;
1310f23b8eeeSSeongJae Park 	struct damon_target *t;
1311f23b8eeeSSeongJae Park 	struct damon_region *r, *next;
1312b9a6ac4eSSeongJae Park 	unsigned int max_nr_accesses = 0;
1313b9a6ac4eSSeongJae Park 	unsigned long sz_limit = 0;
13142224d848SSeongJae Park 
131542e4cef5SChangbin Du 	pr_debug("kdamond (%d) starts\n", current->pid);
13162224d848SSeongJae Park 
1317f7d911c3SSeongJae Park 	if (ctx->ops.init)
1318f7d911c3SSeongJae Park 		ctx->ops.init(ctx);
13192224d848SSeongJae Park 	if (ctx->callback.before_start && ctx->callback.before_start(ctx))
132029454cf6SKaixu Xia 		goto done;
13212224d848SSeongJae Park 
1322b9a6ac4eSSeongJae Park 	sz_limit = damon_region_sz_limit(ctx);
1323b9a6ac4eSSeongJae Park 
132429454cf6SKaixu Xia 	while (!kdamond_need_stop(ctx)) {
132529454cf6SKaixu Xia 		if (kdamond_wait_activation(ctx))
132629454cf6SKaixu Xia 			break;
1327ee801b7dSSeongJae Park 
1328f7d911c3SSeongJae Park 		if (ctx->ops.prepare_access_checks)
1329f7d911c3SSeongJae Park 			ctx->ops.prepare_access_checks(ctx);
13302224d848SSeongJae Park 		if (ctx->callback.after_sampling &&
133129454cf6SKaixu Xia 				ctx->callback.after_sampling(ctx))
133229454cf6SKaixu Xia 			break;
13332224d848SSeongJae Park 
1334cbeaa77bSSeongJae Park 		kdamond_usleep(ctx->attrs.sample_interval);
13352224d848SSeongJae Park 
1336f7d911c3SSeongJae Park 		if (ctx->ops.check_accesses)
1337f7d911c3SSeongJae Park 			max_nr_accesses = ctx->ops.check_accesses(ctx);
13382224d848SSeongJae Park 
13392224d848SSeongJae Park 		if (kdamond_aggregate_interval_passed(ctx)) {
1340b9a6ac4eSSeongJae Park 			kdamond_merge_regions(ctx,
1341b9a6ac4eSSeongJae Park 					max_nr_accesses / 10,
1342b9a6ac4eSSeongJae Park 					sz_limit);
13432224d848SSeongJae Park 			if (ctx->callback.after_aggregation &&
134429454cf6SKaixu Xia 					ctx->callback.after_aggregation(ctx))
134529454cf6SKaixu Xia 				break;
134664517d6eSHuaisheng Ye 			if (!list_empty(&ctx->schemes))
13471f366e42SSeongJae Park 				kdamond_apply_schemes(ctx);
1348f23b8eeeSSeongJae Park 			kdamond_reset_aggregated(ctx);
1349b9a6ac4eSSeongJae Park 			kdamond_split_regions(ctx);
1350f7d911c3SSeongJae Park 			if (ctx->ops.reset_aggregated)
1351f7d911c3SSeongJae Park 				ctx->ops.reset_aggregated(ctx);
13522224d848SSeongJae Park 		}
13532224d848SSeongJae Park 
1354f7d911c3SSeongJae Park 		if (kdamond_need_update_operations(ctx)) {
1355f7d911c3SSeongJae Park 			if (ctx->ops.update)
1356f7d911c3SSeongJae Park 				ctx->ops.update(ctx);
1357b9a6ac4eSSeongJae Park 			sz_limit = damon_region_sz_limit(ctx);
13582224d848SSeongJae Park 		}
13592224d848SSeongJae Park 	}
136029454cf6SKaixu Xia done:
1361f23b8eeeSSeongJae Park 	damon_for_each_target(t, ctx) {
1362f23b8eeeSSeongJae Park 		damon_for_each_region_safe(r, next, t)
1363b9a6ac4eSSeongJae Park 			damon_destroy_region(r, t);
1364f23b8eeeSSeongJae Park 	}
13652224d848SSeongJae Park 
13660f91d133SChangbin Du 	if (ctx->callback.before_terminate)
13670f91d133SChangbin Du 		ctx->callback.before_terminate(ctx);
1368f7d911c3SSeongJae Park 	if (ctx->ops.cleanup)
1369f7d911c3SSeongJae Park 		ctx->ops.cleanup(ctx);
13702224d848SSeongJae Park 
137142e4cef5SChangbin Du 	pr_debug("kdamond (%d) finishes\n", current->pid);
13722224d848SSeongJae Park 	mutex_lock(&ctx->kdamond_lock);
13732224d848SSeongJae Park 	ctx->kdamond = NULL;
13742224d848SSeongJae Park 	mutex_unlock(&ctx->kdamond_lock);
13752224d848SSeongJae Park 
13762224d848SSeongJae Park 	mutex_lock(&damon_lock);
13772224d848SSeongJae Park 	nr_running_ctxs--;
13788b9b0d33SSeongJae Park 	if (!nr_running_ctxs && running_exclusive_ctxs)
13798b9b0d33SSeongJae Park 		running_exclusive_ctxs = false;
13802224d848SSeongJae Park 	mutex_unlock(&damon_lock);
13812224d848SSeongJae Park 
13825f7fe2b9SChangbin Du 	return 0;
13832224d848SSeongJae Park }
138417ccae8bSSeongJae Park 
13850d83b2d8SXin Hao /*
13860d83b2d8SXin Hao  * struct damon_system_ram_region - System RAM resource address region of
13870d83b2d8SXin Hao  *				    [@start, @end).
13880d83b2d8SXin Hao  * @start:	Start address of the region (inclusive).
13890d83b2d8SXin Hao  * @end:	End address of the region (exclusive).
13900d83b2d8SXin Hao  */
13910d83b2d8SXin Hao struct damon_system_ram_region {
13920d83b2d8SXin Hao 	unsigned long start;
13930d83b2d8SXin Hao 	unsigned long end;
13940d83b2d8SXin Hao };
13950d83b2d8SXin Hao 
13960d83b2d8SXin Hao static int walk_system_ram(struct resource *res, void *arg)
13970d83b2d8SXin Hao {
13980d83b2d8SXin Hao 	struct damon_system_ram_region *a = arg;
13990d83b2d8SXin Hao 
14000d83b2d8SXin Hao 	if (a->end - a->start < resource_size(res)) {
14010d83b2d8SXin Hao 		a->start = res->start;
14020d83b2d8SXin Hao 		a->end = res->end;
14030d83b2d8SXin Hao 	}
14040d83b2d8SXin Hao 	return 0;
14050d83b2d8SXin Hao }
14060d83b2d8SXin Hao 
14070d83b2d8SXin Hao /*
14080d83b2d8SXin Hao  * Find biggest 'System RAM' resource and store its start and end address in
14090d83b2d8SXin Hao  * @start and @end, respectively.  If no System RAM is found, returns false.
14100d83b2d8SXin Hao  */
1411233f0b31SKaixu Xia static bool damon_find_biggest_system_ram(unsigned long *start,
1412233f0b31SKaixu Xia 						unsigned long *end)
14130d83b2d8SXin Hao 
14140d83b2d8SXin Hao {
14150d83b2d8SXin Hao 	struct damon_system_ram_region arg = {};
14160d83b2d8SXin Hao 
14170d83b2d8SXin Hao 	walk_system_ram_res(0, ULONG_MAX, &arg, walk_system_ram);
14180d83b2d8SXin Hao 	if (arg.end <= arg.start)
14190d83b2d8SXin Hao 		return false;
14200d83b2d8SXin Hao 
14210d83b2d8SXin Hao 	*start = arg.start;
14220d83b2d8SXin Hao 	*end = arg.end;
14230d83b2d8SXin Hao 	return true;
14240d83b2d8SXin Hao }
14250d83b2d8SXin Hao 
1426233f0b31SKaixu Xia /**
1427233f0b31SKaixu Xia  * damon_set_region_biggest_system_ram_default() - Set the region of the given
1428233f0b31SKaixu Xia  * monitoring target as requested, or biggest 'System RAM'.
1429233f0b31SKaixu Xia  * @t:		The monitoring target to set the region.
1430233f0b31SKaixu Xia  * @start:	The pointer to the start address of the region.
1431233f0b31SKaixu Xia  * @end:	The pointer to the end address of the region.
1432233f0b31SKaixu Xia  *
1433233f0b31SKaixu Xia  * This function sets the region of @t as requested by @start and @end.  If the
1434233f0b31SKaixu Xia  * values of @start and @end are zero, however, this function finds the biggest
1435233f0b31SKaixu Xia  * 'System RAM' resource and sets the region to cover the resource.  In the
1436233f0b31SKaixu Xia  * latter case, this function saves the start and end addresses of the resource
1437233f0b31SKaixu Xia  * in @start and @end, respectively.
1438233f0b31SKaixu Xia  *
1439233f0b31SKaixu Xia  * Return: 0 on success, negative error code otherwise.
1440233f0b31SKaixu Xia  */
1441233f0b31SKaixu Xia int damon_set_region_biggest_system_ram_default(struct damon_target *t,
1442233f0b31SKaixu Xia 			unsigned long *start, unsigned long *end)
1443233f0b31SKaixu Xia {
1444233f0b31SKaixu Xia 	struct damon_addr_range addr_range;
1445233f0b31SKaixu Xia 
1446233f0b31SKaixu Xia 	if (*start > *end)
1447233f0b31SKaixu Xia 		return -EINVAL;
1448233f0b31SKaixu Xia 
1449233f0b31SKaixu Xia 	if (!*start && !*end &&
1450233f0b31SKaixu Xia 		!damon_find_biggest_system_ram(start, end))
1451233f0b31SKaixu Xia 		return -EINVAL;
1452233f0b31SKaixu Xia 
1453233f0b31SKaixu Xia 	addr_range.start = *start;
1454233f0b31SKaixu Xia 	addr_range.end = *end;
1455233f0b31SKaixu Xia 	return damon_set_regions(t, &addr_range, 1);
1456233f0b31SKaixu Xia }
1457233f0b31SKaixu Xia 
1458a1870944SDawei Li static int __init damon_init(void)
1459a1870944SDawei Li {
1460a1870944SDawei Li 	damon_region_cache = KMEM_CACHE(damon_region, 0);
1461a1870944SDawei Li 	if (unlikely(!damon_region_cache)) {
1462a1870944SDawei Li 		pr_err("creating damon_region_cache fails\n");
1463a1870944SDawei Li 		return -ENOMEM;
1464a1870944SDawei Li 	}
1465a1870944SDawei Li 
1466a1870944SDawei Li 	return 0;
1467a1870944SDawei Li }
1468a1870944SDawei Li 
1469a1870944SDawei Li subsys_initcall(damon_init);
1470a1870944SDawei Li 
147117ccae8bSSeongJae Park #include "core-test.h"
1472