1 /* SPDX-License-Identifier: GPL-2.0 */
2 /*
3 * DAMON api
4 */
5
6 #ifndef _DAMON_H_
7 #define _DAMON_H_
8
9 #include <linux/math64.h>
10 #include <linux/memcontrol.h>
11 #include <linux/mutex.h>
12 #include <linux/prandom.h>
13 #include <linux/time64.h>
14 #include <linux/types.h>
15
16 /* Minimal region size. Every damon_region is aligned by this. */
17 #define DAMON_MIN_REGION_SZ PAGE_SIZE
18 /* Maximum number of monitoring probes. */
19 #define DAMON_MAX_PROBES (4)
20 /* Max priority score for DAMON-based operation schemes */
21 #define DAMOS_MAX_SCORE (99)
22
23 /**
24 * struct damon_addr_range - Represents an address region of [@start, @end).
25 * @start: Start address of the region (inclusive).
26 * @end: End address of the region (exclusive).
27 */
28 struct damon_addr_range {
29 unsigned long start;
30 unsigned long end;
31 };
32
33 /**
34 * struct damon_size_range - Represents size for filter to operate on [@min, @max].
35 * @min: Min size (inclusive).
36 * @max: Max size (inclusive).
37 */
38 struct damon_size_range {
39 unsigned long min;
40 unsigned long max;
41 };
42
43 /**
44 * struct damon_region - Represents a monitoring target region.
45 * @ar: The address range of the region.
46 * @sampling_addr: Address of the sample for the next access check.
47 * @nr_accesses: Access frequency of this region.
48 * @nr_accesses_bp: @nr_accesses in basis point (0.01%) that updated for
49 * each sampling interval.
50 * @probe_hits: Number of probe-positive region samples.
51 * @list: List head for siblings.
52 * @age: Age of this region.
53 *
54 * For any use case, @ar should be non-zero positive size.
55 *
56 * @nr_accesses is reset to zero for every &damon_attrs->aggr_interval and be
57 * increased for every &damon_attrs->sample_interval if an access to the region
58 * during the last sampling interval is found. The update of this field should
59 * not be done with direct access but with the helper function,
60 * damon_update_region_access_rate().
61 *
62 * @nr_accesses_bp is another representation of @nr_accesses in basis point
63 * (1 in 10,000) that updated for every &damon_attrs->sample_interval in a
64 * manner similar to moving sum. By the algorithm, this value becomes
65 * @nr_accesses * 10000 for every &struct damon_attrs->aggr_interval. This can
66 * be used when the aggregation interval is too huge and therefore cannot wait
67 * for it before getting the access monitoring results.
68 *
69 * @age is initially zero, increased for each aggregation interval, and reset
70 * to zero again if the access frequency is significantly changed. If two
71 * regions are merged into a new region, both @nr_accesses and @age of the new
72 * region are set as region size-weighted average of those of the two regions.
73 */
74 struct damon_region {
75 struct damon_addr_range ar;
76 unsigned long sampling_addr;
77 unsigned int nr_accesses;
78 unsigned int nr_accesses_bp;
79 unsigned char probe_hits[DAMON_MAX_PROBES];
80 struct list_head list;
81
82 unsigned int age;
83 /* private: Internal value for age calculation. */
84 unsigned int last_nr_accesses;
85 };
86
87 /**
88 * struct damon_target - Represents a monitoring target.
89 * @pid: The PID of the virtual address space to monitor.
90 * @nr_regions: Number of monitoring target regions of this target.
91 * @regions_list: Head of the monitoring target regions of this target.
92 * @list: List head for siblings.
93 * @obsolete: Whether the commit destination target is obsolete.
94 *
95 * Each monitoring context could have multiple targets. For example, a context
96 * for virtual memory address spaces could have multiple target processes. The
97 * @pid should be set for appropriate &struct damon_operations including the
98 * virtual address spaces monitoring operations.
99 *
100 * @obsolete is used only for damon_commit_targets() source targets, to specify
101 * the matching destination targets are obsolete. Read damon_commit_targets()
102 * to see how it is handled.
103 */
104 struct damon_target {
105 struct pid *pid;
106 unsigned int nr_regions;
107 struct list_head regions_list;
108 struct list_head list;
109 bool obsolete;
110 };
111
112 /**
113 * enum damos_action - Represents an action of a Data Access Monitoring-based
114 * Operation Scheme.
115 *
116 * @DAMOS_WILLNEED: Call ``madvise()`` for the region with MADV_WILLNEED.
117 * @DAMOS_COLD: Call ``madvise()`` for the region with MADV_COLD.
118 * @DAMOS_PAGEOUT: Reclaim the region.
119 * @DAMOS_HUGEPAGE: Call ``madvise()`` for the region with MADV_HUGEPAGE.
120 * @DAMOS_NOHUGEPAGE: Call ``madvise()`` for the region with MADV_NOHUGEPAGE.
121 * @DAMOS_COLLAPSE: Call ``madvise()`` for the region with MADV_COLLAPSE.
122 * @DAMOS_LRU_PRIO: Prioritize the region on its LRU lists.
123 * @DAMOS_LRU_DEPRIO: Deprioritize the region on its LRU lists.
124 * @DAMOS_MIGRATE_HOT: Migrate the regions prioritizing warmer regions.
125 * @DAMOS_MIGRATE_COLD: Migrate the regions prioritizing colder regions.
126 * @DAMOS_STAT: Do nothing but count the stat.
127 * @NR_DAMOS_ACTIONS: Total number of DAMOS actions
128 *
129 * The support of each action is up to running &struct damon_operations.
130 * Refer to 'Operation Action' section of Documentation/mm/damon/design.rst for
131 * status of the supports.
132 *
133 * Note that DAMOS_PAGEOUT doesn't trigger demotions.
134 */
135 enum damos_action {
136 DAMOS_WILLNEED,
137 DAMOS_COLD,
138 DAMOS_PAGEOUT,
139 DAMOS_HUGEPAGE,
140 DAMOS_NOHUGEPAGE,
141 DAMOS_COLLAPSE,
142 DAMOS_LRU_PRIO,
143 DAMOS_LRU_DEPRIO,
144 DAMOS_MIGRATE_HOT,
145 DAMOS_MIGRATE_COLD,
146 DAMOS_STAT, /* Do nothing but only record the stat */
147 NR_DAMOS_ACTIONS,
148 };
149
150 /**
151 * enum damos_quota_goal_metric - Represents the metric to be used as the goal
152 *
153 * @DAMOS_QUOTA_USER_INPUT: User-input value.
154 * @DAMOS_QUOTA_SOME_MEM_PSI_US: System level some memory PSI in us.
155 * @DAMOS_QUOTA_NODE_MEM_USED_BP: MemUsed ratio of a node.
156 * @DAMOS_QUOTA_NODE_MEM_FREE_BP: MemFree ratio of a node.
157 * @DAMOS_QUOTA_NODE_MEMCG_USED_BP: MemUsed ratio of a node for a cgroup.
158 * @DAMOS_QUOTA_NODE_MEMCG_FREE_BP: MemFree ratio of a node for a cgroup.
159 * @DAMOS_QUOTA_ACTIVE_MEM_BP: Active to total LRU memory ratio.
160 * @DAMOS_QUOTA_INACTIVE_MEM_BP: Inactive to total LRU memory ratio.
161 * @DAMOS_QUOTA_NODE_ELIGIBLE_MEM_BP: Scheme-eligible memory ratio of a
162 * node in basis points (0-10000).
163 * @NR_DAMOS_QUOTA_GOAL_METRICS: Number of DAMOS quota goal metrics.
164 *
165 * Metrics equal to larger than @NR_DAMOS_QUOTA_GOAL_METRICS are unsupported.
166 */
167 enum damos_quota_goal_metric {
168 DAMOS_QUOTA_USER_INPUT,
169 DAMOS_QUOTA_SOME_MEM_PSI_US,
170 DAMOS_QUOTA_NODE_MEM_USED_BP,
171 DAMOS_QUOTA_NODE_MEM_FREE_BP,
172 DAMOS_QUOTA_NODE_MEMCG_USED_BP,
173 DAMOS_QUOTA_NODE_MEMCG_FREE_BP,
174 DAMOS_QUOTA_ACTIVE_MEM_BP,
175 DAMOS_QUOTA_INACTIVE_MEM_BP,
176 DAMOS_QUOTA_NODE_ELIGIBLE_MEM_BP,
177 NR_DAMOS_QUOTA_GOAL_METRICS,
178 };
179
180 /**
181 * struct damos_quota_goal - DAMOS scheme quota auto-tuning goal.
182 * @metric: Metric to be used for representing the goal.
183 * @target_value: Target value of @metric to achieve with the tuning.
184 * @current_value: Current value of @metric.
185 * @last_psi_total: Last measured total PSI
186 * @nid: Node id.
187 * @memcg_id: Memcg id.
188 * @list: List head for siblings.
189 *
190 * Data structure for getting the current score of the quota tuning goal. The
191 * score is calculated by how close @current_value and @target_value are. Then
192 * the score is entered to DAMON's internal feedback loop mechanism to get the
193 * auto-tuned quota.
194 *
195 * If @metric is DAMOS_QUOTA_USER_INPUT, @current_value should be manually
196 * entered by the user, probably inside the kdamond callbacks. Otherwise,
197 * DAMON sets @current_value with self-measured value of @metric.
198 *
199 * If @metric is DAMOS_QUOTA_NODE_MEM_{USED,FREE}_BP, @nid represents the node
200 * id of the target node to account the used/free memory.
201 *
202 * If @metric is DAMOS_QUOTA_NODE_MEMCG_{USED,FREE}_BP, @nid and @memcg_id
203 * represents the node id and the cgroup to account the used memory for.
204 */
205 struct damos_quota_goal {
206 enum damos_quota_goal_metric metric;
207 unsigned long target_value;
208 unsigned long current_value;
209 /* metric-dependent fields */
210 union {
211 u64 last_psi_total;
212 struct {
213 int nid;
214 u64 memcg_id;
215 };
216 };
217 struct list_head list;
218 };
219
220 /**
221 * enum damos_quota_goal_tuner - Goal-based quota tuning logic.
222 * @DAMOS_QUOTA_GOAL_TUNER_CONSIST: Aim long term consistent quota.
223 * @DAMOS_QUOTA_GOAL_TUNER_TEMPORAL: Aim zero quota asap.
224 */
225 enum damos_quota_goal_tuner {
226 DAMOS_QUOTA_GOAL_TUNER_CONSIST,
227 DAMOS_QUOTA_GOAL_TUNER_TEMPORAL,
228 };
229
230 /**
231 * struct damos_quota - Controls the aggressiveness of the given scheme.
232 * @reset_interval: Charge reset interval in milliseconds.
233 * @ms: Maximum milliseconds that the scheme can use.
234 * @sz: Maximum bytes of memory that the action can be applied.
235 * @goals: Head of quota tuning goals (&damos_quota_goal) list.
236 * @goal_tuner: Goal-based @esz tuning algorithm to use.
237 * @esz: Effective size quota in bytes.
238 * @fail_charge_num: Failed regions charge rate numerator.
239 * @fail_charge_denom: Failed regions charge rate denominator.
240 *
241 * @weight_sz: Weight of the region's size for prioritization.
242 * @weight_nr_accesses: Weight of the region's nr_accesses for prioritization.
243 * @weight_age: Weight of the region's age for prioritization.
244 *
245 * To avoid consuming too much CPU time or IO resources for applying the
246 * &struct damos->action to large memory, DAMON allows users to set time and/or
247 * size quotas. The quotas can be set by writing non-zero values to &ms and
248 * &sz, respectively. If the time quota is set, DAMON tries to use only up to
249 * &ms milliseconds within &reset_interval for applying the action. If the
250 * size quota is set, DAMON tries to apply the action only up to &sz bytes
251 * within &reset_interval.
252 *
253 * To convince the different types of quotas and goals, DAMON internally
254 * converts those into one single size quota called "effective quota". DAMON
255 * internally uses it as the only one real quota. The conversion is made as
256 * follows.
257 *
258 * The time quota is transformed to a size quota using estimated throughput of
259 * the scheme's action. DAMON then compares it against &sz and uses smaller
260 * one as the effective quota.
261 *
262 * If @goals is not empty, DAMON calculates yet another size quota based on the
263 * goals using its internal feedback loop algorithm, for every @reset_interval.
264 * Then, if the new size quota is smaller than the effective quota, it uses the
265 * new size quota as the effective quota.
266 *
267 * The resulting effective size quota in bytes is set to @esz.
268 *
269 * For DAMOS action applying failed amount of regions, charging those same to
270 * those that the action has successfully applied may be unfair. For the
271 * reason, 'the size * @fail_charge_num / @fail_charge_denom' is charged.
272 *
273 * For selecting regions within the quota, DAMON prioritizes current scheme's
274 * target memory regions using the &struct damon_operations->get_scheme_score.
275 * You could customize the prioritization logic by setting &weight_sz,
276 * &weight_nr_accesses, and &weight_age, because monitoring operations are
277 * encouraged to respect those.
278 */
279 struct damos_quota {
280 unsigned long reset_interval;
281 unsigned long ms;
282 unsigned long sz;
283 struct list_head goals;
284 enum damos_quota_goal_tuner goal_tuner;
285 unsigned long esz;
286
287 unsigned int fail_charge_num;
288 unsigned int fail_charge_denom;
289
290 unsigned int weight_sz;
291 unsigned int weight_nr_accesses;
292 unsigned int weight_age;
293
294 /* private: */
295 /* For throughput estimation */
296 unsigned long total_charged_sz;
297 unsigned long total_charged_ns;
298
299 /* For charging the quota */
300 unsigned long charged_sz;
301 unsigned long charged_from;
302 struct damon_target *charge_target_from;
303 unsigned long charge_addr_from;
304
305 /* For prioritization */
306 unsigned int min_score;
307
308 /* For feedback loop */
309 unsigned long esz_bp;
310 };
311
312 /**
313 * enum damos_wmark_metric - Represents the watermark metric.
314 *
315 * @DAMOS_WMARK_NONE: Ignore the watermarks of the given scheme.
316 * @DAMOS_WMARK_FREE_MEM_RATE: Free memory rate of the system in [0,1000].
317 * @NR_DAMOS_WMARK_METRICS: Total number of DAMOS watermark metrics
318 */
319 enum damos_wmark_metric {
320 DAMOS_WMARK_NONE,
321 DAMOS_WMARK_FREE_MEM_RATE,
322 NR_DAMOS_WMARK_METRICS,
323 };
324
325 /**
326 * struct damos_watermarks - Controls when a given scheme should be activated.
327 * @metric: Metric for the watermarks.
328 * @interval: Watermarks check time interval in microseconds.
329 * @high: High watermark.
330 * @mid: Middle watermark.
331 * @low: Low watermark.
332 *
333 * If &metric is &DAMOS_WMARK_NONE, the scheme is always active. Being active
334 * means DAMON does monitoring and applying the action of the scheme to
335 * appropriate memory regions. Else, DAMON checks &metric of the system for at
336 * least every &interval microseconds and works as below.
337 *
338 * If &metric is higher than &high, the scheme is inactivated. If &metric is
339 * between &mid and &low, the scheme is activated. If &metric is lower than
340 * &low, the scheme is inactivated.
341 */
342 struct damos_watermarks {
343 enum damos_wmark_metric metric;
344 unsigned long interval;
345 unsigned long high;
346 unsigned long mid;
347 unsigned long low;
348
349 /* private: */
350 bool activated;
351 };
352
353 /**
354 * struct damos_stat - Statistics on a given scheme.
355 * @nr_tried: Total number of regions that the scheme is tried to be applied.
356 * @sz_tried: Total size of regions that the scheme is tried to be applied.
357 * @nr_applied: Total number of regions that the scheme is applied.
358 * @sz_applied: Total size of regions that the scheme is applied.
359 * @sz_ops_filter_passed:
360 * Total bytes that passed ops layer-handled DAMOS filters.
361 * @qt_exceeds: Total number of times the quota of the scheme has exceeded.
362 * @nr_snapshots:
363 * Total number of DAMON snapshots that the scheme has tried.
364 *
365 * "Tried an action to a region" in this context means the DAMOS core logic
366 * determined the region as eligible to apply the action. The access pattern
367 * (&struct damos_access_pattern), quotas (&struct damos_quota), watermarks
368 * (&struct damos_watermarks) and filters (&struct damos_filter) that handled
369 * on core logic can affect this. The core logic asks the operation set
370 * (&struct damon_operations) to apply the action to the region.
371 *
372 * "Applied an action to a region" in this context means the operation set
373 * (&struct damon_operations) successfully applied the action to the region, at
374 * least to a part of the region. The filters (&struct damos_filter) that
375 * handled on operation set layer and type of the action and pages of the
376 * region can affect this. For example, if a filter is set to exclude
377 * anonymous pages and the region has only anonymous pages, the region will be
378 * failed at applying the action. If the action is &DAMOS_PAGEOUT and all
379 * pages of the region are already paged out, the region will be failed at
380 * applying the action.
381 */
382 struct damos_stat {
383 unsigned long nr_tried;
384 unsigned long sz_tried;
385 unsigned long nr_applied;
386 unsigned long sz_applied;
387 unsigned long sz_ops_filter_passed;
388 unsigned long qt_exceeds;
389 unsigned long nr_snapshots;
390 };
391
392 /**
393 * enum damos_filter_type - Type of memory for &struct damos_filter
394 * @DAMOS_FILTER_TYPE_ANON: Anonymous pages.
395 * @DAMOS_FILTER_TYPE_ACTIVE: Active pages.
396 * @DAMOS_FILTER_TYPE_MEMCG: Specific memcg's pages.
397 * @DAMOS_FILTER_TYPE_YOUNG: Recently accessed pages.
398 * @DAMOS_FILTER_TYPE_HUGEPAGE_SIZE: Page is part of a hugepage.
399 * @DAMOS_FILTER_TYPE_UNMAPPED: Unmapped pages.
400 * @DAMOS_FILTER_TYPE_ADDR: Address range.
401 * @DAMOS_FILTER_TYPE_TARGET: Data Access Monitoring target.
402 * @NR_DAMOS_FILTER_TYPES: Number of filter types.
403 *
404 * The anon pages type and memcg type filters are handled by underlying
405 * &struct damon_operations as a part of scheme action trying, and therefore
406 * accounted as 'tried'. In contrast, other types are handled by core layer
407 * before trying of the action and therefore not accounted as 'tried'.
408 *
409 * The support of the filters that handled by &struct damon_operations depend
410 * on the running &struct damon_operations.
411 * &enum DAMON_OPS_PADDR supports both anon pages type and memcg type filters,
412 * while &enum DAMON_OPS_VADDR and &enum DAMON_OPS_FVADDR don't support any of
413 * the two types.
414 */
415 enum damos_filter_type {
416 DAMOS_FILTER_TYPE_ANON,
417 DAMOS_FILTER_TYPE_ACTIVE,
418 DAMOS_FILTER_TYPE_MEMCG,
419 DAMOS_FILTER_TYPE_YOUNG,
420 DAMOS_FILTER_TYPE_HUGEPAGE_SIZE,
421 DAMOS_FILTER_TYPE_UNMAPPED,
422 DAMOS_FILTER_TYPE_ADDR,
423 DAMOS_FILTER_TYPE_TARGET,
424 NR_DAMOS_FILTER_TYPES,
425 };
426
427 /**
428 * struct damos_filter - DAMOS action target memory filter.
429 * @type: Type of the target memory.
430 * @matching: Whether this is for @type-matching memory.
431 * @allow: Whether to include or exclude the @matching memory.
432 * @memcg_id: Memcg id of the question if @type is DAMOS_FILTER_MEMCG.
433 * @addr_range: Address range if @type is DAMOS_FILTER_TYPE_ADDR.
434 * @target_idx: Index of the &struct damon_target of
435 * &damon_ctx->adaptive_targets if @type is
436 * DAMOS_FILTER_TYPE_TARGET.
437 * @sz_range: Size range if @type is DAMOS_FILTER_TYPE_HUGEPAGE_SIZE.
438 * @list: List head for siblings.
439 *
440 * Before applying the &damos->action to a memory region, DAMOS checks if each
441 * byte of the region matches to this given condition and avoid applying the
442 * action if so. Support of each filter type depends on the running &struct
443 * damon_operations and the type. Refer to &enum damos_filter_type for more
444 * details.
445 */
446 struct damos_filter {
447 enum damos_filter_type type;
448 bool matching;
449 bool allow;
450 union {
451 u64 memcg_id;
452 struct damon_addr_range addr_range;
453 int target_idx;
454 struct damon_size_range sz_range;
455 };
456 struct list_head list;
457 };
458
459 struct damon_ctx;
460 struct damos;
461
462 /**
463 * struct damos_walk_control - Control damos_walk().
464 *
465 * @walk_fn: Function to be called back for each region.
466 * @data: Data that will be passed to walk functions.
467 *
468 * Control damos_walk(), which requests specific kdamond to invoke the given
469 * function to each region that eligible to apply actions of the kdamond's
470 * schemes. Refer to damos_walk() for more details.
471 */
472 struct damos_walk_control {
473 void (*walk_fn)(void *data, struct damon_ctx *ctx,
474 struct damon_target *t, struct damon_region *r,
475 struct damos *s, unsigned long sz_filter_passed);
476 void *data;
477 /* private: internal use only */
478 /* informs if the kdamond finished handling of the walk request */
479 struct completion completion;
480 /* informs if the walk is canceled. */
481 bool canceled;
482 };
483
484 /**
485 * struct damos_access_pattern - Target access pattern of the given scheme.
486 * @min_sz_region: Minimum size of target regions.
487 * @max_sz_region: Maximum size of target regions.
488 * @min_nr_accesses: Minimum ``->nr_accesses`` of target regions.
489 * @max_nr_accesses: Maximum ``->nr_accesses`` of target regions.
490 * @min_age_region: Minimum age of target regions.
491 * @max_age_region: Maximum age of target regions.
492 */
493 struct damos_access_pattern {
494 unsigned long min_sz_region;
495 unsigned long max_sz_region;
496 unsigned int min_nr_accesses;
497 unsigned int max_nr_accesses;
498 unsigned int min_age_region;
499 unsigned int max_age_region;
500 };
501
502 /**
503 * struct damos_migrate_dests - Migration destination nodes and their weights.
504 * @node_id_arr: Array of migration destination node ids.
505 * @weight_arr: Array of migration weights for @node_id_arr.
506 * @nr_dests: Length of the @node_id_arr and @weight_arr arrays.
507 *
508 * @node_id_arr is an array of the ids of migration destination nodes.
509 * @weight_arr is an array of the weights for those. The weights in
510 * @weight_arr are for nodes in @node_id_arr of same array index.
511 */
512 struct damos_migrate_dests {
513 unsigned int *node_id_arr;
514 unsigned int *weight_arr;
515 size_t nr_dests;
516 };
517
518 /**
519 * struct damos - Represents a Data Access Monitoring-based Operation Scheme.
520 * @pattern: Access pattern of target regions.
521 * @action: &damos_action to be applied to the target regions.
522 * @apply_interval_us: The time between applying the @action.
523 * @quota: Control the aggressiveness of this scheme.
524 * @wmarks: Watermarks for automated (in)activation of this scheme.
525 * @migrate_dests: Destination nodes if @action is "migrate_{hot,cold}".
526 * @target_nid: Destination node if @action is "migrate_{hot,cold}".
527 * @core_filters: Additional set of &struct damos_filter for &action.
528 * @ops_filters: ops layer handling &struct damos_filter objects list.
529 * @last_applied: Last @action applied ops-managing entity.
530 * @stat: Statistics of this scheme.
531 * @max_nr_snapshots: Upper limit of nr_snapshots stat.
532 * @list: List head for siblings.
533 *
534 * For each @apply_interval_us, DAMON finds regions which fit in the
535 * &pattern and applies &action to those. To avoid consuming too much
536 * CPU time or IO resources for the &action, "a is used.
537 *
538 * If @apply_interval_us is zero, &damon_attrs->aggr_interval is used instead.
539 *
540 * To do the work only when needed, schemes can be activated for specific
541 * system situations using &wmarks. If all schemes that registered to the
542 * monitoring context are inactive, DAMON stops monitoring either, and just
543 * repeatedly checks the watermarks.
544 *
545 * @migrate_dests specifies multiple migration target nodes with different
546 * weights for migrate_hot or migrate_cold actions. @target_nid is ignored if
547 * this is set.
548 *
549 * @target_nid is used to set the migration target node for migrate_hot or
550 * migrate_cold actions, and @migrate_dests is unset.
551 *
552 * Before applying the &action to a memory region, &struct damon_operations
553 * implementation could check pages of the region and skip &action to respect
554 * &core_filters
555 *
556 * The minimum entity that @action can be applied depends on the underlying
557 * &struct damon_operations. Since it may not be aligned with the core layer
558 * abstract, namely &struct damon_region, &struct damon_operations could apply
559 * @action to same entity multiple times. Large folios that underlying on
560 * multiple &struct damon region objects could be such examples. The &struct
561 * damon_operations can use @last_applied to avoid that. DAMOS core logic
562 * unsets @last_applied when each regions walking for applying the scheme is
563 * finished.
564 *
565 * After applying the &action to each region, &stat is updated.
566 *
567 * If &max_nr_snapshots is set as non-zero and &stat.nr_snapshots be same to or
568 * greater than it, the scheme is deactivated.
569 */
570 struct damos {
571 struct damos_access_pattern pattern;
572 enum damos_action action;
573 unsigned long apply_interval_us;
574 /* private: internal use only */
575 /*
576 * number of sample intervals that should be passed before applying
577 * @action
578 */
579 unsigned long next_apply_sis;
580 /* informs if ongoing DAMOS walk for this scheme is finished */
581 bool walk_completed;
582 /*
583 * If the current region in the filtering stage is allowed by core
584 * layer-handled filters. If true, operations layer allows it, too.
585 */
586 bool core_filters_allowed;
587 /* whether to reject core/ops filters umatched regions */
588 bool core_filters_default_reject;
589 bool ops_filters_default_reject;
590 /* public: */
591 struct damos_quota quota;
592 struct damos_watermarks wmarks;
593 union {
594 struct {
595 int target_nid;
596 struct damos_migrate_dests migrate_dests;
597 };
598 };
599 struct list_head core_filters;
600 struct list_head ops_filters;
601 void *last_applied;
602 struct damos_stat stat;
603 unsigned long max_nr_snapshots;
604 struct list_head list;
605 };
606
607 /**
608 * enum damon_ops_id - Identifier for each monitoring operations implementation
609 *
610 * @DAMON_OPS_VADDR: Monitoring operations for virtual address spaces
611 * @DAMON_OPS_FVADDR: Monitoring operations for only fixed ranges of virtual
612 * address spaces
613 * @DAMON_OPS_PADDR: Monitoring operations for the physical address space
614 * @NR_DAMON_OPS: Number of monitoring operations implementations
615 */
616 enum damon_ops_id {
617 DAMON_OPS_VADDR,
618 DAMON_OPS_FVADDR,
619 DAMON_OPS_PADDR,
620 NR_DAMON_OPS,
621 };
622
623 /**
624 * struct damon_operations - Monitoring operations for given use cases.
625 *
626 * @id: Identifier of this operations set.
627 * @init: Initialize operations-related data structures.
628 * @update: Update operations-related data structures.
629 * @prepare_access_checks: Prepare next access check of target regions.
630 * @check_accesses: Check the accesses to target regions.
631 * @apply_probes: Apply probes for each region.
632 * @get_scheme_score: Get the score of a region for a scheme.
633 * @apply_scheme: Apply a DAMON-based operation scheme.
634 * @target_valid: Determine if the target is valid.
635 * @cleanup_target: Clean up each target before deallocation.
636 *
637 * DAMON can be extended for various address spaces and usages. For this,
638 * users should register the low level operations for their target address
639 * space and usecase via the &damon_ctx.ops. Then, the monitoring thread
640 * (&damon_ctx.kdamond) calls @init and @prepare_access_checks before starting
641 * the monitoring, @update after each &damon_attrs.ops_update_interval, and
642 * @check_accesses, @target_valid and @prepare_access_checks after each
643 * &damon_attrs.sample_interval.
644 *
645 * Each &struct damon_operations instance having valid @id can be registered
646 * via damon_register_ops() and selected by damon_select_ops() later.
647 * @init should initialize operations-related data structures. For example,
648 * this could be used to construct proper monitoring target regions and link
649 * those to @damon_ctx.adaptive_targets.
650 * @update should update the operations-related data structures. For example,
651 * this could be used to update monitoring target regions for current status.
652 * @prepare_access_checks should manipulate the monitoring regions to be
653 * prepared for the next access check.
654 * @check_accesses should check the accesses to each region that made after the
655 * last preparation and update the number of observed accesses of each region.
656 * It should also return max number of observed accesses that made as a result
657 * of its update. The value will be used for regions adjustment threshold.
658 * @apply_probes should apply the data attribute probes to each region and
659 * accordingly update the probe hits counter of the region.
660 * @get_scheme_score should return the priority score of a region for a scheme
661 * as an integer in [0, &DAMOS_MAX_SCORE].
662 * @apply_scheme is called from @kdamond when a region for user provided
663 * DAMON-based operation scheme is found. It should apply the scheme's action
664 * to the region and return bytes of the region that the action is successfully
665 * applied. It should also report how many bytes of the region has passed
666 * filters (&struct damos_filter) that handled by itself.
667 * @target_valid should check whether the target is still valid for the
668 * monitoring.
669 * @cleanup_target is called before the target will be deallocated.
670 */
671 struct damon_operations {
672 enum damon_ops_id id;
673 void (*init)(struct damon_ctx *context);
674 void (*update)(struct damon_ctx *context);
675 void (*prepare_access_checks)(struct damon_ctx *context);
676 unsigned int (*check_accesses)(struct damon_ctx *context);
677 void (*apply_probes)(struct damon_ctx *context);
678 int (*get_scheme_score)(struct damon_ctx *context,
679 struct damon_region *r, struct damos *scheme);
680 unsigned long (*apply_scheme)(struct damon_ctx *context,
681 struct damon_target *t, struct damon_region *r,
682 struct damos *scheme, unsigned long *sz_filter_passed);
683 bool (*target_valid)(struct damon_target *t);
684 void (*cleanup_target)(struct damon_target *t);
685 };
686
687 /*
688 * struct damon_call_control - Control damon_call().
689 *
690 * @fn: Function to be called back.
691 * @data: Data that will be passed to @fn.
692 * @repeat: Repeat invocations.
693 * @return_code: Return code from @fn invocation.
694 * @dealloc_on_cancel: If @repeat is true, de-allocate when canceled.
695 *
696 * Control damon_call(), which requests specific kdamond to invoke a given
697 * function. Refer to damon_call() for more details.
698 */
699 struct damon_call_control {
700 int (*fn)(void *data);
701 void *data;
702 bool repeat;
703 int return_code;
704 bool dealloc_on_cancel;
705 /* private: internal use only */
706 /* informs if the kdamond finished handling of the request */
707 struct completion completion;
708 /* informs if the kdamond canceled @fn infocation */
709 bool canceled;
710 /* List head for siblings. */
711 struct list_head list;
712 };
713
714 /**
715 * struct damon_intervals_goal - Monitoring intervals auto-tuning goal.
716 *
717 * @access_bp: Access events observation ratio to achieve in bp.
718 * @aggrs: Number of aggregations to achieve @access_bp within.
719 * @min_sample_us: Minimum resulting sampling interval in microseconds.
720 * @max_sample_us: Maximum resulting sampling interval in microseconds.
721 *
722 * DAMON automatically tunes &damon_attrs->sample_interval and
723 * &damon_attrs->aggr_interval aiming the ratio in bp (1/10,000) of
724 * DAMON-observed access events to theoretical maximum amount within @aggrs
725 * aggregations be same to @access_bp. The logic increases
726 * &damon_attrs->aggr_interval and &damon_attrs->sampling_interval in same
727 * ratio if the current access events observation ratio is lower than the
728 * target for each @aggrs aggregations, and vice versa.
729 *
730 * If @aggrs is zero, the tuning is disabled and hence this struct is ignored.
731 */
732 struct damon_intervals_goal {
733 unsigned long access_bp;
734 unsigned long aggrs;
735 unsigned long min_sample_us;
736 unsigned long max_sample_us;
737 };
738
739 /**
740 * enum damon_filter_type - Type of &struct damon_filter
741 *
742 * @DAMON_FILTER_TYPE_ANON: Anonymous pages.
743 * @DAMON_FILTER_TYPE_MEMCG: Specific memcg's pages.
744 */
745 enum damon_filter_type {
746 DAMON_FILTER_TYPE_ANON,
747 DAMON_FILTER_TYPE_MEMCG,
748 };
749
750 /**
751 * struct damon_filter - DAMON region filter for &struct damon_probe.
752 *
753 * @type: Type of the region.
754 * @matching: Whether this filter is for the type-matching ones.
755 * @allow: Whether the @type-@matching ones should pass this filter.
756 * @memcg_id: Memcg id of the question if @type is DAMON_FILTER_MEMCG.
757 * @list: Siblings list.
758 */
759 struct damon_filter {
760 enum damon_filter_type type;
761 bool matching;
762 bool allow;
763 union {
764 u64 memcg_id;
765 };
766 struct list_head list;
767 };
768
769 /**
770 * struct damon_probe - Data region attribute probe.
771 *
772 * @filters: Filters for assessing if a given region is for this probe.
773 * @list: Siblings list.
774 */
775 struct damon_probe {
776 struct list_head filters;
777 struct list_head list;
778 };
779
780 /**
781 * struct damon_attrs - Monitoring attributes for accuracy/overhead control.
782 *
783 * @sample_interval: The time between access samplings.
784 * @aggr_interval: The time between monitor results aggregations.
785 * @ops_update_interval: The time between monitoring operations updates.
786 * @intervals_goal: Intervals auto-tuning goal.
787 * @min_nr_regions: The minimum number of adaptive monitoring
788 * regions.
789 * @max_nr_regions: The maximum number of adaptive monitoring
790 * regions.
791 *
792 * For each @sample_interval, DAMON checks whether each region is accessed or
793 * not during the last @sample_interval. If such access is found, DAMON
794 * aggregates the information by increasing &damon_region->nr_accesses for
795 * @aggr_interval time. For each @aggr_interval, the count is reset. DAMON
796 * also checks whether the target memory regions need update (e.g., by
797 * ``mmap()`` calls from the application, in case of virtual memory monitoring)
798 * and applies the changes for each @ops_update_interval. All time intervals
799 * are in micro-seconds. Please refer to &struct damon_operations and &struct
800 * damon_call_control for more detail.
801 */
802 struct damon_attrs {
803 unsigned long sample_interval;
804 unsigned long aggr_interval;
805 unsigned long ops_update_interval;
806 struct damon_intervals_goal intervals_goal;
807 unsigned long min_nr_regions;
808 unsigned long max_nr_regions;
809 /* private: internal use only */
810 /*
811 * @aggr_interval to @sample_interval ratio.
812 * Core-external components call damon_set_attrs() with &damon_attrs
813 * that this field is unset. In the case, damon_set_attrs() sets this
814 * field of resulting &damon_attrs. Core-internal components such as
815 * kdamond_tune_intervals() calls damon_set_attrs() with &damon_attrs
816 * that this field is set. In the case, damon_set_attrs() just keep
817 * it.
818 */
819 unsigned long aggr_samples;
820 };
821
822 /**
823 * struct damon_ctx - Represents a context for each monitoring. This is the
824 * main interface that allows users to set the attributes and get the results
825 * of the monitoring.
826 *
827 * @attrs: Monitoring attributes for accuracy/overhead control.
828 *
829 * For each monitoring context, one kernel thread for the monitoring, namely
830 * kdamond, is created. The pid of kdamond can be retrieved using
831 * damon_kdamond_pid().
832 *
833 * Once started, kdamond runs until explicitly required to be terminated or
834 * every monitoring target is invalid. The validity of the targets is checked
835 * via the &damon_operations.target_valid of @ops. The termination can also be
836 * explicitly requested by calling damon_stop(). To know if a kdamond is
837 * running, damon_is_running() can be used.
838 *
839 * While the kdamond is running, all accesses to &struct damon_ctx from a
840 * thread other than the kdamond should be made using safe DAMON APIs,
841 * including damon_call() and damos_walk().
842 *
843 * @ops: Set of monitoring operations for given use cases.
844 * @probes: Head of probes (&damon_probe) list.
845 * @addr_unit: Scale factor for core to ops address conversion.
846 * @min_region_sz: Minimum region size.
847 * @pause: Pause kdamond main loop.
848 * @adaptive_targets: Head of monitoring targets (&damon_target) list.
849 * @schemes: Head of schemes (&damos) list.
850 * @rnd_state: Per-ctx PRNG state for damon_rand().
851 */
852 struct damon_ctx {
853 struct damon_attrs attrs;
854
855 /* private: internal use only */
856 /* number of sample intervals that passed since this context started */
857 unsigned long passed_sample_intervals;
858 /*
859 * number of sample intervals that should be passed before next
860 * aggregation
861 */
862 unsigned long next_aggregation_sis;
863 /*
864 * number of sample intervals that should be passed before next ops
865 * update
866 */
867 unsigned long next_ops_update_sis;
868 /*
869 * number of sample intervals that should be passed before next
870 * intervals tuning
871 */
872 unsigned long next_intervals_tune_sis;
873 /* for waiting until the execution of the kdamond_fn is started */
874 struct completion kdamond_started;
875 /* for scheme quotas prioritization */
876 unsigned long *regions_score_histogram;
877
878 /* lists of &struct damon_call_control */
879 struct list_head call_controls;
880 bool call_controls_obsolete;
881 struct mutex call_controls_lock;
882
883 struct damos_walk_control *walk_control;
884 bool walk_control_obsolete;
885 struct mutex walk_control_lock;
886
887 /*
888 * indicate if this may be corrupted. Currentonly this is set only for
889 * damon_commit_ctx() failure.
890 */
891 bool maybe_corrupted;
892
893 /* Working thread of the given DAMON context */
894 struct task_struct *kdamond;
895 /* Protects @kdamond field access */
896 struct mutex kdamond_lock;
897
898 /* public: */
899 struct damon_operations ops;
900 struct list_head probes;
901 unsigned long addr_unit;
902 unsigned long min_region_sz;
903 bool pause;
904
905 struct list_head adaptive_targets;
906 struct list_head schemes;
907
908 struct rnd_state rnd_state;
909 };
910
911 /* Get a random number in [@l, @r) using @ctx's lockless PRNG. */
damon_rand(struct damon_ctx * ctx,unsigned long l,unsigned long r)912 static inline unsigned long damon_rand(struct damon_ctx *ctx,
913 unsigned long l, unsigned long r)
914 {
915 unsigned long span = r - l;
916 u64 rnd;
917
918 if (span <= U32_MAX) {
919 rnd = prandom_u32_state(&ctx->rnd_state);
920 return l + (unsigned long)((rnd * span) >> 32);
921 }
922 rnd = ((u64)prandom_u32_state(&ctx->rnd_state) << 32) |
923 prandom_u32_state(&ctx->rnd_state);
924 return l + mul_u64_u64_shr(rnd, span, 64);
925 }
926
damon_next_region(struct damon_region * r)927 static inline struct damon_region *damon_next_region(struct damon_region *r)
928 {
929 return container_of(r->list.next, struct damon_region, list);
930 }
931
damon_prev_region(struct damon_region * r)932 static inline struct damon_region *damon_prev_region(struct damon_region *r)
933 {
934 return container_of(r->list.prev, struct damon_region, list);
935 }
936
damon_last_region(struct damon_target * t)937 static inline struct damon_region *damon_last_region(struct damon_target *t)
938 {
939 return list_last_entry(&t->regions_list, struct damon_region, list);
940 }
941
damon_first_region(struct damon_target * t)942 static inline struct damon_region *damon_first_region(struct damon_target *t)
943 {
944 return list_first_entry(&t->regions_list, struct damon_region, list);
945 }
946
damon_sz_region(struct damon_region * r)947 static inline unsigned long damon_sz_region(struct damon_region *r)
948 {
949 return r->ar.end - r->ar.start;
950 }
951
952 #define damon_for_each_filter(f, p) \
953 list_for_each_entry(f, &(p)->filters, list)
954
955 #define damon_for_each_filter_safe(f, next, p) \
956 list_for_each_entry_safe(f, next, &(p)->filters, list)
957
958 #define damon_for_each_probe(p, ctx) \
959 list_for_each_entry(p, &(ctx)->probes, list)
960
961 #define damon_for_each_probe_safe(p, next, ctx) \
962 list_for_each_entry_safe(p, next, &(ctx)->probes, list)
963
964 #define damon_for_each_region(r, t) \
965 list_for_each_entry(r, &(t)->regions_list, list)
966
967 #define damon_for_each_region_from(r, t) \
968 list_for_each_entry_from(r, &(t)->regions_list, list)
969
970 #define damon_for_each_region_safe(r, next, t) \
971 list_for_each_entry_safe(r, next, &(t)->regions_list, list)
972
973 #define damon_for_each_target(t, ctx) \
974 list_for_each_entry(t, &(ctx)->adaptive_targets, list)
975
976 #define damon_for_each_target_safe(t, next, ctx) \
977 list_for_each_entry_safe(t, next, &(ctx)->adaptive_targets, list)
978
979 #define damon_for_each_scheme(s, ctx) \
980 list_for_each_entry(s, &(ctx)->schemes, list)
981
982 #define damon_for_each_scheme_safe(s, next, ctx) \
983 list_for_each_entry_safe(s, next, &(ctx)->schemes, list)
984
985 #define damos_for_each_quota_goal(goal, quota) \
986 list_for_each_entry(goal, &(quota)->goals, list)
987
988 #define damos_for_each_quota_goal_safe(goal, next, quota) \
989 list_for_each_entry_safe(goal, next, &(quota)->goals, list)
990
991 #define damos_for_each_core_filter(f, scheme) \
992 list_for_each_entry(f, &(scheme)->core_filters, list)
993
994 #define damos_for_each_core_filter_safe(f, next, scheme) \
995 list_for_each_entry_safe(f, next, &(scheme)->core_filters, list)
996
997 #define damos_for_each_ops_filter(f, scheme) \
998 list_for_each_entry(f, &(scheme)->ops_filters, list)
999
1000 #define damos_for_each_ops_filter_safe(f, next, scheme) \
1001 list_for_each_entry_safe(f, next, &(scheme)->ops_filters, list)
1002
1003 #ifdef CONFIG_DAMON
1004
1005 struct damon_filter *damon_new_filter(enum damon_filter_type type,
1006 bool matching, bool allow);
1007 void damon_add_filter(struct damon_probe *probe, struct damon_filter *f);
1008 void damon_destroy_filter(struct damon_filter *f);
1009
1010 struct damon_probe *damon_new_probe(void);
1011 void damon_add_probe(struct damon_ctx *ctx, struct damon_probe *probe);
1012
1013 struct damon_region *damon_new_region(unsigned long start, unsigned long end);
1014
1015 int damon_set_regions(struct damon_target *t, struct damon_addr_range *ranges,
1016 unsigned int nr_ranges, unsigned long min_region_sz);
1017 void damon_update_region_access_rate(struct damon_region *r, bool accessed,
1018 struct damon_attrs *attrs);
1019
1020 struct damos_filter *damos_new_filter(enum damos_filter_type type,
1021 bool matching, bool allow);
1022 void damos_add_filter(struct damos *s, struct damos_filter *f);
1023 bool damos_filter_for_ops(enum damos_filter_type type);
1024 void damos_destroy_filter(struct damos_filter *f);
1025
1026 struct damos_quota_goal *damos_new_quota_goal(
1027 enum damos_quota_goal_metric metric,
1028 unsigned long target_value);
1029 void damos_add_quota_goal(struct damos_quota *q, struct damos_quota_goal *g);
1030 void damos_destroy_quota_goal(struct damos_quota_goal *goal);
1031
1032 struct damos *damon_new_scheme(struct damos_access_pattern *pattern,
1033 enum damos_action action,
1034 unsigned long apply_interval_us,
1035 struct damos_quota *quota,
1036 struct damos_watermarks *wmarks,
1037 int target_nid);
1038 void damon_add_scheme(struct damon_ctx *ctx, struct damos *s);
1039 void damon_destroy_scheme(struct damos *s);
1040 int damos_commit_quota_goals(struct damos_quota *dst, struct damos_quota *src);
1041
1042 struct damon_target *damon_new_target(void);
1043 void damon_add_target(struct damon_ctx *ctx, struct damon_target *t);
1044 bool damon_targets_empty(struct damon_ctx *ctx);
1045 void damon_free_target(struct damon_target *t);
1046 void damon_destroy_target(struct damon_target *t, struct damon_ctx *ctx);
1047 unsigned int damon_nr_regions(struct damon_target *t);
1048
1049 struct damon_ctx *damon_new_ctx(void);
1050 void damon_destroy_ctx(struct damon_ctx *ctx);
1051 int damon_set_attrs(struct damon_ctx *ctx, struct damon_attrs *attrs);
1052 void damon_set_schemes(struct damon_ctx *ctx,
1053 struct damos **schemes, ssize_t nr_schemes);
1054 int damon_commit_ctx(struct damon_ctx *old_ctx, struct damon_ctx *new_ctx);
1055 int damon_nr_running_ctxs(void);
1056 bool damon_is_registered_ops(enum damon_ops_id id);
1057 int damon_register_ops(struct damon_operations *ops);
1058 int damon_select_ops(struct damon_ctx *ctx, enum damon_ops_id id);
1059
damon_target_has_pid(const struct damon_ctx * ctx)1060 static inline bool damon_target_has_pid(const struct damon_ctx *ctx)
1061 {
1062 return ctx->ops.id == DAMON_OPS_VADDR || ctx->ops.id == DAMON_OPS_FVADDR;
1063 }
1064
damon_max_nr_accesses(const struct damon_attrs * attrs)1065 static inline unsigned int damon_max_nr_accesses(const struct damon_attrs *attrs)
1066 {
1067 unsigned long sample_interval;
1068 unsigned long max_nr_accesses;
1069
1070 sample_interval = attrs->sample_interval ? : 1;
1071 max_nr_accesses = min(attrs->aggr_interval / sample_interval,
1072 (unsigned long)UINT_MAX);
1073 return max_nr_accesses ? : 1;
1074 }
1075
1076
1077 bool damon_initialized(void);
1078 int damon_start(struct damon_ctx **ctxs, int nr_ctxs, bool exclusive);
1079 int damon_stop(struct damon_ctx **ctxs, int nr_ctxs);
1080 bool damon_is_running(struct damon_ctx *ctx);
1081 int damon_kdamond_pid(struct damon_ctx *ctx);
1082
1083 int damon_call(struct damon_ctx *ctx, struct damon_call_control *control);
1084 int damos_walk(struct damon_ctx *ctx, struct damos_walk_control *control);
1085
1086 int damon_set_region_system_rams_default(struct damon_target *t,
1087 unsigned long *start, unsigned long *end,
1088 unsigned long addr_unit,
1089 unsigned long min_region_sz);
1090
1091 #endif /* CONFIG_DAMON */
1092
1093 #endif /* _DAMON_H */
1094