3efbe80779db2a227a976ff0d6027d2d605b200f
[linux-2.6-microblaze.git] / mm / damon / core.c
1 // SPDX-License-Identifier: GPL-2.0
2 /*
3  * Data Access Monitor
4  *
5  * Author: SeongJae Park <sjpark@amazon.de>
6  */
7
8 #define pr_fmt(fmt) "damon: " fmt
9
10 #include <linux/damon.h>
11 #include <linux/delay.h>
12 #include <linux/kthread.h>
13 #include <linux/random.h>
14 #include <linux/slab.h>
15
16 #define CREATE_TRACE_POINTS
17 #include <trace/events/damon.h>
18
19 #ifdef CONFIG_DAMON_KUNIT_TEST
20 #undef DAMON_MIN_REGION
21 #define DAMON_MIN_REGION 1
22 #endif
23
24 /* Get a random number in [l, r) */
25 #define damon_rand(l, r) (l + prandom_u32_max(r - l))
26
27 static DEFINE_MUTEX(damon_lock);
28 static int nr_running_ctxs;
29
30 /*
31  * Construct a damon_region struct
32  *
33  * Returns the pointer to the new struct if success, or NULL otherwise
34  */
35 struct damon_region *damon_new_region(unsigned long start, unsigned long end)
36 {
37         struct damon_region *region;
38
39         region = kmalloc(sizeof(*region), GFP_KERNEL);
40         if (!region)
41                 return NULL;
42
43         region->ar.start = start;
44         region->ar.end = end;
45         region->nr_accesses = 0;
46         INIT_LIST_HEAD(&region->list);
47
48         region->age = 0;
49         region->last_nr_accesses = 0;
50
51         return region;
52 }
53
54 /*
55  * Add a region between two other regions
56  */
57 inline void damon_insert_region(struct damon_region *r,
58                 struct damon_region *prev, struct damon_region *next,
59                 struct damon_target *t)
60 {
61         __list_add(&r->list, &prev->list, &next->list);
62         t->nr_regions++;
63 }
64
65 void damon_add_region(struct damon_region *r, struct damon_target *t)
66 {
67         list_add_tail(&r->list, &t->regions_list);
68         t->nr_regions++;
69 }
70
71 static void damon_del_region(struct damon_region *r, struct damon_target *t)
72 {
73         list_del(&r->list);
74         t->nr_regions--;
75 }
76
77 static void damon_free_region(struct damon_region *r)
78 {
79         kfree(r);
80 }
81
82 void damon_destroy_region(struct damon_region *r, struct damon_target *t)
83 {
84         damon_del_region(r, t);
85         damon_free_region(r);
86 }
87
88 /*
89  * Construct a damon_target struct
90  *
91  * Returns the pointer to the new struct if success, or NULL otherwise
92  */
93 struct damon_target *damon_new_target(unsigned long id)
94 {
95         struct damon_target *t;
96
97         t = kmalloc(sizeof(*t), GFP_KERNEL);
98         if (!t)
99                 return NULL;
100
101         t->id = id;
102         t->nr_regions = 0;
103         INIT_LIST_HEAD(&t->regions_list);
104
105         return t;
106 }
107
108 void damon_add_target(struct damon_ctx *ctx, struct damon_target *t)
109 {
110         list_add_tail(&t->list, &ctx->adaptive_targets);
111 }
112
113 static void damon_del_target(struct damon_target *t)
114 {
115         list_del(&t->list);
116 }
117
118 void damon_free_target(struct damon_target *t)
119 {
120         struct damon_region *r, *next;
121
122         damon_for_each_region_safe(r, next, t)
123                 damon_free_region(r);
124         kfree(t);
125 }
126
127 void damon_destroy_target(struct damon_target *t)
128 {
129         damon_del_target(t);
130         damon_free_target(t);
131 }
132
133 unsigned int damon_nr_regions(struct damon_target *t)
134 {
135         return t->nr_regions;
136 }
137
138 struct damon_ctx *damon_new_ctx(void)
139 {
140         struct damon_ctx *ctx;
141
142         ctx = kzalloc(sizeof(*ctx), GFP_KERNEL);
143         if (!ctx)
144                 return NULL;
145
146         ctx->sample_interval = 5 * 1000;
147         ctx->aggr_interval = 100 * 1000;
148         ctx->primitive_update_interval = 60 * 1000 * 1000;
149
150         ktime_get_coarse_ts64(&ctx->last_aggregation);
151         ctx->last_primitive_update = ctx->last_aggregation;
152
153         mutex_init(&ctx->kdamond_lock);
154
155         ctx->min_nr_regions = 10;
156         ctx->max_nr_regions = 1000;
157
158         INIT_LIST_HEAD(&ctx->adaptive_targets);
159
160         return ctx;
161 }
162
163 static void damon_destroy_targets(struct damon_ctx *ctx)
164 {
165         struct damon_target *t, *next_t;
166
167         if (ctx->primitive.cleanup) {
168                 ctx->primitive.cleanup(ctx);
169                 return;
170         }
171
172         damon_for_each_target_safe(t, next_t, ctx)
173                 damon_destroy_target(t);
174 }
175
176 void damon_destroy_ctx(struct damon_ctx *ctx)
177 {
178         damon_destroy_targets(ctx);
179         kfree(ctx);
180 }
181
182 /**
183  * damon_set_targets() - Set monitoring targets.
184  * @ctx:        monitoring context
185  * @ids:        array of target ids
186  * @nr_ids:     number of entries in @ids
187  *
188  * This function should not be called while the kdamond is running.
189  *
190  * Return: 0 on success, negative error code otherwise.
191  */
192 int damon_set_targets(struct damon_ctx *ctx,
193                       unsigned long *ids, ssize_t nr_ids)
194 {
195         ssize_t i;
196         struct damon_target *t, *next;
197
198         damon_destroy_targets(ctx);
199
200         for (i = 0; i < nr_ids; i++) {
201                 t = damon_new_target(ids[i]);
202                 if (!t) {
203                         pr_err("Failed to alloc damon_target\n");
204                         /* The caller should do cleanup of the ids itself */
205                         damon_for_each_target_safe(t, next, ctx)
206                                 damon_destroy_target(t);
207                         return -ENOMEM;
208                 }
209                 damon_add_target(ctx, t);
210         }
211
212         return 0;
213 }
214
215 /**
216  * damon_set_attrs() - Set attributes for the monitoring.
217  * @ctx:                monitoring context
218  * @sample_int:         time interval between samplings
219  * @aggr_int:           time interval between aggregations
220  * @primitive_upd_int:  time interval between monitoring primitive updates
221  * @min_nr_reg:         minimal number of regions
222  * @max_nr_reg:         maximum number of regions
223  *
224  * This function should not be called while the kdamond is running.
225  * Every time interval is in micro-seconds.
226  *
227  * Return: 0 on success, negative error code otherwise.
228  */
229 int damon_set_attrs(struct damon_ctx *ctx, unsigned long sample_int,
230                     unsigned long aggr_int, unsigned long primitive_upd_int,
231                     unsigned long min_nr_reg, unsigned long max_nr_reg)
232 {
233         if (min_nr_reg < 3) {
234                 pr_err("min_nr_regions (%lu) must be at least 3\n",
235                                 min_nr_reg);
236                 return -EINVAL;
237         }
238         if (min_nr_reg > max_nr_reg) {
239                 pr_err("invalid nr_regions.  min (%lu) > max (%lu)\n",
240                                 min_nr_reg, max_nr_reg);
241                 return -EINVAL;
242         }
243
244         ctx->sample_interval = sample_int;
245         ctx->aggr_interval = aggr_int;
246         ctx->primitive_update_interval = primitive_upd_int;
247         ctx->min_nr_regions = min_nr_reg;
248         ctx->max_nr_regions = max_nr_reg;
249
250         return 0;
251 }
252
253 /**
254  * damon_nr_running_ctxs() - Return number of currently running contexts.
255  */
256 int damon_nr_running_ctxs(void)
257 {
258         int nr_ctxs;
259
260         mutex_lock(&damon_lock);
261         nr_ctxs = nr_running_ctxs;
262         mutex_unlock(&damon_lock);
263
264         return nr_ctxs;
265 }
266
267 /* Returns the size upper limit for each monitoring region */
268 static unsigned long damon_region_sz_limit(struct damon_ctx *ctx)
269 {
270         struct damon_target *t;
271         struct damon_region *r;
272         unsigned long sz = 0;
273
274         damon_for_each_target(t, ctx) {
275                 damon_for_each_region(r, t)
276                         sz += r->ar.end - r->ar.start;
277         }
278
279         if (ctx->min_nr_regions)
280                 sz /= ctx->min_nr_regions;
281         if (sz < DAMON_MIN_REGION)
282                 sz = DAMON_MIN_REGION;
283
284         return sz;
285 }
286
287 static bool damon_kdamond_running(struct damon_ctx *ctx)
288 {
289         bool running;
290
291         mutex_lock(&ctx->kdamond_lock);
292         running = ctx->kdamond != NULL;
293         mutex_unlock(&ctx->kdamond_lock);
294
295         return running;
296 }
297
298 static int kdamond_fn(void *data);
299
300 /*
301  * __damon_start() - Starts monitoring with given context.
302  * @ctx:        monitoring context
303  *
304  * This function should be called while damon_lock is hold.
305  *
306  * Return: 0 on success, negative error code otherwise.
307  */
308 static int __damon_start(struct damon_ctx *ctx)
309 {
310         int err = -EBUSY;
311
312         mutex_lock(&ctx->kdamond_lock);
313         if (!ctx->kdamond) {
314                 err = 0;
315                 ctx->kdamond_stop = false;
316                 ctx->kdamond = kthread_run(kdamond_fn, ctx, "kdamond.%d",
317                                 nr_running_ctxs);
318                 if (IS_ERR(ctx->kdamond)) {
319                         err = PTR_ERR(ctx->kdamond);
320                         ctx->kdamond = NULL;
321                 }
322         }
323         mutex_unlock(&ctx->kdamond_lock);
324
325         return err;
326 }
327
328 /**
329  * damon_start() - Starts the monitorings for a given group of contexts.
330  * @ctxs:       an array of the pointers for contexts to start monitoring
331  * @nr_ctxs:    size of @ctxs
332  *
333  * This function starts a group of monitoring threads for a group of monitoring
334  * contexts.  One thread per each context is created and run in parallel.  The
335  * caller should handle synchronization between the threads by itself.  If a
336  * group of threads that created by other 'damon_start()' call is currently
337  * running, this function does nothing but returns -EBUSY.
338  *
339  * Return: 0 on success, negative error code otherwise.
340  */
341 int damon_start(struct damon_ctx **ctxs, int nr_ctxs)
342 {
343         int i;
344         int err = 0;
345
346         mutex_lock(&damon_lock);
347         if (nr_running_ctxs) {
348                 mutex_unlock(&damon_lock);
349                 return -EBUSY;
350         }
351
352         for (i = 0; i < nr_ctxs; i++) {
353                 err = __damon_start(ctxs[i]);
354                 if (err)
355                         break;
356                 nr_running_ctxs++;
357         }
358         mutex_unlock(&damon_lock);
359
360         return err;
361 }
362
363 /*
364  * __damon_stop() - Stops monitoring of given context.
365  * @ctx:        monitoring context
366  *
367  * Return: 0 on success, negative error code otherwise.
368  */
369 static int __damon_stop(struct damon_ctx *ctx)
370 {
371         mutex_lock(&ctx->kdamond_lock);
372         if (ctx->kdamond) {
373                 ctx->kdamond_stop = true;
374                 mutex_unlock(&ctx->kdamond_lock);
375                 while (damon_kdamond_running(ctx))
376                         usleep_range(ctx->sample_interval,
377                                         ctx->sample_interval * 2);
378                 return 0;
379         }
380         mutex_unlock(&ctx->kdamond_lock);
381
382         return -EPERM;
383 }
384
385 /**
386  * damon_stop() - Stops the monitorings for a given group of contexts.
387  * @ctxs:       an array of the pointers for contexts to stop monitoring
388  * @nr_ctxs:    size of @ctxs
389  *
390  * Return: 0 on success, negative error code otherwise.
391  */
392 int damon_stop(struct damon_ctx **ctxs, int nr_ctxs)
393 {
394         int i, err = 0;
395
396         for (i = 0; i < nr_ctxs; i++) {
397                 /* nr_running_ctxs is decremented in kdamond_fn */
398                 err = __damon_stop(ctxs[i]);
399                 if (err)
400                         return err;
401         }
402
403         return err;
404 }
405
406 /*
407  * damon_check_reset_time_interval() - Check if a time interval is elapsed.
408  * @baseline:   the time to check whether the interval has elapsed since
409  * @interval:   the time interval (microseconds)
410  *
411  * See whether the given time interval has passed since the given baseline
412  * time.  If so, it also updates the baseline to current time for next check.
413  *
414  * Return:      true if the time interval has passed, or false otherwise.
415  */
416 static bool damon_check_reset_time_interval(struct timespec64 *baseline,
417                 unsigned long interval)
418 {
419         struct timespec64 now;
420
421         ktime_get_coarse_ts64(&now);
422         if ((timespec64_to_ns(&now) - timespec64_to_ns(baseline)) <
423                         interval * 1000)
424                 return false;
425         *baseline = now;
426         return true;
427 }
428
429 /*
430  * Check whether it is time to flush the aggregated information
431  */
432 static bool kdamond_aggregate_interval_passed(struct damon_ctx *ctx)
433 {
434         return damon_check_reset_time_interval(&ctx->last_aggregation,
435                         ctx->aggr_interval);
436 }
437
438 /*
439  * Reset the aggregated monitoring results ('nr_accesses' of each region).
440  */
441 static void kdamond_reset_aggregated(struct damon_ctx *c)
442 {
443         struct damon_target *t;
444
445         damon_for_each_target(t, c) {
446                 struct damon_region *r;
447
448                 damon_for_each_region(r, t) {
449                         trace_damon_aggregated(t, r, damon_nr_regions(t));
450                         r->last_nr_accesses = r->nr_accesses;
451                         r->nr_accesses = 0;
452                 }
453         }
454 }
455
456 #define sz_damon_region(r) (r->ar.end - r->ar.start)
457
458 /*
459  * Merge two adjacent regions into one region
460  */
461 static void damon_merge_two_regions(struct damon_target *t,
462                 struct damon_region *l, struct damon_region *r)
463 {
464         unsigned long sz_l = sz_damon_region(l), sz_r = sz_damon_region(r);
465
466         l->nr_accesses = (l->nr_accesses * sz_l + r->nr_accesses * sz_r) /
467                         (sz_l + sz_r);
468         l->age = (l->age * sz_l + r->age * sz_r) / (sz_l + sz_r);
469         l->ar.end = r->ar.end;
470         damon_destroy_region(r, t);
471 }
472
473 #define diff_of(a, b) (a > b ? a - b : b - a)
474
475 /*
476  * Merge adjacent regions having similar access frequencies
477  *
478  * t            target affected by this merge operation
479  * thres        '->nr_accesses' diff threshold for the merge
480  * sz_limit     size upper limit of each region
481  */
482 static void damon_merge_regions_of(struct damon_target *t, unsigned int thres,
483                                    unsigned long sz_limit)
484 {
485         struct damon_region *r, *prev = NULL, *next;
486
487         damon_for_each_region_safe(r, next, t) {
488                 if (diff_of(r->nr_accesses, r->last_nr_accesses) > thres)
489                         r->age = 0;
490                 else
491                         r->age++;
492
493                 if (prev && prev->ar.end == r->ar.start &&
494                     diff_of(prev->nr_accesses, r->nr_accesses) <= thres &&
495                     sz_damon_region(prev) + sz_damon_region(r) <= sz_limit)
496                         damon_merge_two_regions(t, prev, r);
497                 else
498                         prev = r;
499         }
500 }
501
502 /*
503  * Merge adjacent regions having similar access frequencies
504  *
505  * threshold    '->nr_accesses' diff threshold for the merge
506  * sz_limit     size upper limit of each region
507  *
508  * This function merges monitoring target regions which are adjacent and their
509  * access frequencies are similar.  This is for minimizing the monitoring
510  * overhead under the dynamically changeable access pattern.  If a merge was
511  * unnecessarily made, later 'kdamond_split_regions()' will revert it.
512  */
513 static void kdamond_merge_regions(struct damon_ctx *c, unsigned int threshold,
514                                   unsigned long sz_limit)
515 {
516         struct damon_target *t;
517
518         damon_for_each_target(t, c)
519                 damon_merge_regions_of(t, threshold, sz_limit);
520 }
521
522 /*
523  * Split a region in two
524  *
525  * r            the region to be split
526  * sz_r         size of the first sub-region that will be made
527  */
528 static void damon_split_region_at(struct damon_ctx *ctx,
529                 struct damon_target *t, struct damon_region *r,
530                 unsigned long sz_r)
531 {
532         struct damon_region *new;
533
534         new = damon_new_region(r->ar.start + sz_r, r->ar.end);
535         if (!new)
536                 return;
537
538         r->ar.end = new->ar.start;
539
540         new->age = r->age;
541         new->last_nr_accesses = r->last_nr_accesses;
542
543         damon_insert_region(new, r, damon_next_region(r), t);
544 }
545
546 /* Split every region in the given target into 'nr_subs' regions */
547 static void damon_split_regions_of(struct damon_ctx *ctx,
548                                      struct damon_target *t, int nr_subs)
549 {
550         struct damon_region *r, *next;
551         unsigned long sz_region, sz_sub = 0;
552         int i;
553
554         damon_for_each_region_safe(r, next, t) {
555                 sz_region = r->ar.end - r->ar.start;
556
557                 for (i = 0; i < nr_subs - 1 &&
558                                 sz_region > 2 * DAMON_MIN_REGION; i++) {
559                         /*
560                          * Randomly select size of left sub-region to be at
561                          * least 10 percent and at most 90% of original region
562                          */
563                         sz_sub = ALIGN_DOWN(damon_rand(1, 10) *
564                                         sz_region / 10, DAMON_MIN_REGION);
565                         /* Do not allow blank region */
566                         if (sz_sub == 0 || sz_sub >= sz_region)
567                                 continue;
568
569                         damon_split_region_at(ctx, t, r, sz_sub);
570                         sz_region = sz_sub;
571                 }
572         }
573 }
574
575 /*
576  * Split every target region into randomly-sized small regions
577  *
578  * This function splits every target region into random-sized small regions if
579  * current total number of the regions is equal or smaller than half of the
580  * user-specified maximum number of regions.  This is for maximizing the
581  * monitoring accuracy under the dynamically changeable access patterns.  If a
582  * split was unnecessarily made, later 'kdamond_merge_regions()' will revert
583  * it.
584  */
585 static void kdamond_split_regions(struct damon_ctx *ctx)
586 {
587         struct damon_target *t;
588         unsigned int nr_regions = 0;
589         static unsigned int last_nr_regions;
590         int nr_subregions = 2;
591
592         damon_for_each_target(t, ctx)
593                 nr_regions += damon_nr_regions(t);
594
595         if (nr_regions > ctx->max_nr_regions / 2)
596                 return;
597
598         /* Maybe the middle of the region has different access frequency */
599         if (last_nr_regions == nr_regions &&
600                         nr_regions < ctx->max_nr_regions / 3)
601                 nr_subregions = 3;
602
603         damon_for_each_target(t, ctx)
604                 damon_split_regions_of(ctx, t, nr_subregions);
605
606         last_nr_regions = nr_regions;
607 }
608
609 /*
610  * Check whether it is time to check and apply the target monitoring regions
611  *
612  * Returns true if it is.
613  */
614 static bool kdamond_need_update_primitive(struct damon_ctx *ctx)
615 {
616         return damon_check_reset_time_interval(&ctx->last_primitive_update,
617                         ctx->primitive_update_interval);
618 }
619
620 /*
621  * Check whether current monitoring should be stopped
622  *
623  * The monitoring is stopped when either the user requested to stop, or all
624  * monitoring targets are invalid.
625  *
626  * Returns true if need to stop current monitoring.
627  */
628 static bool kdamond_need_stop(struct damon_ctx *ctx)
629 {
630         struct damon_target *t;
631         bool stop;
632
633         mutex_lock(&ctx->kdamond_lock);
634         stop = ctx->kdamond_stop;
635         mutex_unlock(&ctx->kdamond_lock);
636         if (stop)
637                 return true;
638
639         if (!ctx->primitive.target_valid)
640                 return false;
641
642         damon_for_each_target(t, ctx) {
643                 if (ctx->primitive.target_valid(t))
644                         return false;
645         }
646
647         return true;
648 }
649
650 static void set_kdamond_stop(struct damon_ctx *ctx)
651 {
652         mutex_lock(&ctx->kdamond_lock);
653         ctx->kdamond_stop = true;
654         mutex_unlock(&ctx->kdamond_lock);
655 }
656
657 /*
658  * The monitoring daemon that runs as a kernel thread
659  */
660 static int kdamond_fn(void *data)
661 {
662         struct damon_ctx *ctx = (struct damon_ctx *)data;
663         struct damon_target *t;
664         struct damon_region *r, *next;
665         unsigned int max_nr_accesses = 0;
666         unsigned long sz_limit = 0;
667
668         pr_debug("kdamond (%d) starts\n", current->pid);
669
670         if (ctx->primitive.init)
671                 ctx->primitive.init(ctx);
672         if (ctx->callback.before_start && ctx->callback.before_start(ctx))
673                 set_kdamond_stop(ctx);
674
675         sz_limit = damon_region_sz_limit(ctx);
676
677         while (!kdamond_need_stop(ctx)) {
678                 if (ctx->primitive.prepare_access_checks)
679                         ctx->primitive.prepare_access_checks(ctx);
680                 if (ctx->callback.after_sampling &&
681                                 ctx->callback.after_sampling(ctx))
682                         set_kdamond_stop(ctx);
683
684                 usleep_range(ctx->sample_interval, ctx->sample_interval + 1);
685
686                 if (ctx->primitive.check_accesses)
687                         max_nr_accesses = ctx->primitive.check_accesses(ctx);
688
689                 if (kdamond_aggregate_interval_passed(ctx)) {
690                         kdamond_merge_regions(ctx,
691                                         max_nr_accesses / 10,
692                                         sz_limit);
693                         if (ctx->callback.after_aggregation &&
694                                         ctx->callback.after_aggregation(ctx))
695                                 set_kdamond_stop(ctx);
696                         kdamond_reset_aggregated(ctx);
697                         kdamond_split_regions(ctx);
698                         if (ctx->primitive.reset_aggregated)
699                                 ctx->primitive.reset_aggregated(ctx);
700                 }
701
702                 if (kdamond_need_update_primitive(ctx)) {
703                         if (ctx->primitive.update)
704                                 ctx->primitive.update(ctx);
705                         sz_limit = damon_region_sz_limit(ctx);
706                 }
707         }
708         damon_for_each_target(t, ctx) {
709                 damon_for_each_region_safe(r, next, t)
710                         damon_destroy_region(r, t);
711         }
712
713         if (ctx->callback.before_terminate &&
714                         ctx->callback.before_terminate(ctx))
715                 set_kdamond_stop(ctx);
716         if (ctx->primitive.cleanup)
717                 ctx->primitive.cleanup(ctx);
718
719         pr_debug("kdamond (%d) finishes\n", current->pid);
720         mutex_lock(&ctx->kdamond_lock);
721         ctx->kdamond = NULL;
722         mutex_unlock(&ctx->kdamond_lock);
723
724         mutex_lock(&damon_lock);
725         nr_running_ctxs--;
726         mutex_unlock(&damon_lock);
727
728         return 0;
729 }
730
731 #include "core-test.h"