// SPDX-License-Identifier: GPL-2.0 /* * Data Access Monitor * * Author: SeongJae Park <[email protected]> */ #define pr_fmt(fmt) … #include <linux/damon.h> #include <linux/delay.h> #include <linux/kthread.h> #include <linux/mm.h> #include <linux/psi.h> #include <linux/slab.h> #include <linux/string.h> #define CREATE_TRACE_POINTS #include <trace/events/damon.h> #ifdef CONFIG_DAMON_KUNIT_TEST #undef DAMON_MIN_REGION #define DAMON_MIN_REGION … #endif static DEFINE_MUTEX(damon_lock); static int nr_running_ctxs; static bool running_exclusive_ctxs; static DEFINE_MUTEX(damon_ops_lock); static struct damon_operations damon_registered_ops[NR_DAMON_OPS]; static struct kmem_cache *damon_region_cache __ro_after_init; /* Should be called under damon_ops_lock with id smaller than NR_DAMON_OPS */ static bool __damon_is_registered_ops(enum damon_ops_id id) { … } /** * damon_is_registered_ops() - Check if a given damon_operations is registered. * @id: Id of the damon_operations to check if registered. * * Return: true if the ops is set, false otherwise. */ bool damon_is_registered_ops(enum damon_ops_id id) { … } /** * damon_register_ops() - Register a monitoring operations set to DAMON. * @ops: monitoring operations set to register. * * This function registers a monitoring operations set of valid &struct * damon_operations->id so that others can find and use them later. * * Return: 0 on success, negative error code otherwise. */ int damon_register_ops(struct damon_operations *ops) { … } /** * damon_select_ops() - Select a monitoring operations to use with the context. * @ctx: monitoring context to use the operations. * @id: id of the registered monitoring operations to select. * * This function finds registered monitoring operations set of @id and make * @ctx to use it. * * Return: 0 on success, negative error code otherwise. */ int damon_select_ops(struct damon_ctx *ctx, enum damon_ops_id id) { … } /* * Construct a damon_region struct * * Returns the pointer to the new struct if success, or NULL otherwise */ struct damon_region *damon_new_region(unsigned long start, unsigned long end) { … } void damon_add_region(struct damon_region *r, struct damon_target *t) { … } static void damon_del_region(struct damon_region *r, struct damon_target *t) { … } static void damon_free_region(struct damon_region *r) { … } void damon_destroy_region(struct damon_region *r, struct damon_target *t) { … } /* * Check whether a region is intersecting an address range * * Returns true if it is. */ static bool damon_intersect(struct damon_region *r, struct damon_addr_range *re) { … } /* * Fill holes in regions with new regions. */ static int damon_fill_regions_holes(struct damon_region *first, struct damon_region *last, struct damon_target *t) { … } /* * damon_set_regions() - Set regions of a target for given address ranges. * @t: the given target. * @ranges: array of new monitoring target ranges. * @nr_ranges: length of @ranges. * * This function adds new regions to, or modify existing regions of a * monitoring target to fit in specific ranges. * * Return: 0 if success, or negative error code otherwise. */ int damon_set_regions(struct damon_target *t, struct damon_addr_range *ranges, unsigned int nr_ranges) { … } struct damos_filter *damos_new_filter(enum damos_filter_type type, bool matching) { … } void damos_add_filter(struct damos *s, struct damos_filter *f) { … } static void damos_del_filter(struct damos_filter *f) { … } static void damos_free_filter(struct damos_filter *f) { … } void damos_destroy_filter(struct damos_filter *f) { … } struct damos_quota_goal *damos_new_quota_goal( enum damos_quota_goal_metric metric, unsigned long target_value) { … } void damos_add_quota_goal(struct damos_quota *q, struct damos_quota_goal *g) { … } static void damos_del_quota_goal(struct damos_quota_goal *g) { … } static void damos_free_quota_goal(struct damos_quota_goal *g) { … } void damos_destroy_quota_goal(struct damos_quota_goal *g) { … } /* initialize fields of @quota that normally API users wouldn't set */ static struct damos_quota *damos_quota_init(struct damos_quota *quota) { … } struct damos *damon_new_scheme(struct damos_access_pattern *pattern, enum damos_action action, unsigned long apply_interval_us, struct damos_quota *quota, struct damos_watermarks *wmarks, int target_nid) { … } static void damos_set_next_apply_sis(struct damos *s, struct damon_ctx *ctx) { … } void damon_add_scheme(struct damon_ctx *ctx, struct damos *s) { … } static void damon_del_scheme(struct damos *s) { … } static void damon_free_scheme(struct damos *s) { … } void damon_destroy_scheme(struct damos *s) { … } /* * Construct a damon_target struct * * Returns the pointer to the new struct if success, or NULL otherwise */ struct damon_target *damon_new_target(void) { … } void damon_add_target(struct damon_ctx *ctx, struct damon_target *t) { … } bool damon_targets_empty(struct damon_ctx *ctx) { … } static void damon_del_target(struct damon_target *t) { … } void damon_free_target(struct damon_target *t) { … } void damon_destroy_target(struct damon_target *t) { … } unsigned int damon_nr_regions(struct damon_target *t) { … } struct damon_ctx *damon_new_ctx(void) { … } static void damon_destroy_targets(struct damon_ctx *ctx) { … } void damon_destroy_ctx(struct damon_ctx *ctx) { … } static unsigned int damon_age_for_new_attrs(unsigned int age, struct damon_attrs *old_attrs, struct damon_attrs *new_attrs) { … } /* convert access ratio in bp (per 10,000) to nr_accesses */ static unsigned int damon_accesses_bp_to_nr_accesses( unsigned int accesses_bp, struct damon_attrs *attrs) { … } /* convert nr_accesses to access ratio in bp (per 10,000) */ static unsigned int damon_nr_accesses_to_accesses_bp( unsigned int nr_accesses, struct damon_attrs *attrs) { … } static unsigned int damon_nr_accesses_for_new_attrs(unsigned int nr_accesses, struct damon_attrs *old_attrs, struct damon_attrs *new_attrs) { … } static void damon_update_monitoring_result(struct damon_region *r, struct damon_attrs *old_attrs, struct damon_attrs *new_attrs) { … } /* * region->nr_accesses is the number of sampling intervals in the last * aggregation interval that access to the region has found, and region->age is * the number of aggregation intervals that its access pattern has maintained. * For the reason, the real meaning of the two fields depend on current * sampling interval and aggregation interval. This function updates * ->nr_accesses and ->age of given damon_ctx's regions for new damon_attrs. */ static void damon_update_monitoring_results(struct damon_ctx *ctx, struct damon_attrs *new_attrs) { … } /** * damon_set_attrs() - Set attributes for the monitoring. * @ctx: monitoring context * @attrs: monitoring attributes * * This function should be called while the kdamond is not running, or an * access check results aggregation is not ongoing (e.g., from * &struct damon_callback->after_aggregation or * &struct damon_callback->after_wmarks_check callbacks). * * Every time interval is in micro-seconds. * * Return: 0 on success, negative error code otherwise. */ int damon_set_attrs(struct damon_ctx *ctx, struct damon_attrs *attrs) { … } /** * damon_set_schemes() - Set data access monitoring based operation schemes. * @ctx: monitoring context * @schemes: array of the schemes * @nr_schemes: number of entries in @schemes * * This function should not be called while the kdamond of the context is * running. */ void damon_set_schemes(struct damon_ctx *ctx, struct damos **schemes, ssize_t nr_schemes) { … } static struct damos_quota_goal *damos_nth_quota_goal( int n, struct damos_quota *q) { … } static void damos_commit_quota_goal( struct damos_quota_goal *dst, struct damos_quota_goal *src) { … } /** * damos_commit_quota_goals() - Commit DAMOS quota goals to another quota. * @dst: The commit destination DAMOS quota. * @src: The commit source DAMOS quota. * * Copies user-specified parameters for quota goals from @src to @dst. Users * should use this function for quota goals-level parameters update of running * DAMON contexts, instead of manual in-place updates. * * This function should be called from parameters-update safe context, like * DAMON callbacks. */ int damos_commit_quota_goals(struct damos_quota *dst, struct damos_quota *src) { … } static int damos_commit_quota(struct damos_quota *dst, struct damos_quota *src) { … } static struct damos_filter *damos_nth_filter(int n, struct damos *s) { … } static void damos_commit_filter_arg( struct damos_filter *dst, struct damos_filter *src) { … } static void damos_commit_filter( struct damos_filter *dst, struct damos_filter *src) { … } static int damos_commit_filters(struct damos *dst, struct damos *src) { … } static struct damos *damon_nth_scheme(int n, struct damon_ctx *ctx) { … } static int damos_commit(struct damos *dst, struct damos *src) { … } static int damon_commit_schemes(struct damon_ctx *dst, struct damon_ctx *src) { … } static struct damon_target *damon_nth_target(int n, struct damon_ctx *ctx) { … } /* * The caller should ensure the regions of @src are * 1. valid (end >= src) and * 2. sorted by starting address. * * If @src has no region, @dst keeps current regions. */ static int damon_commit_target_regions( struct damon_target *dst, struct damon_target *src) { … } static int damon_commit_target( struct damon_target *dst, bool dst_has_pid, struct damon_target *src, bool src_has_pid) { … } static int damon_commit_targets( struct damon_ctx *dst, struct damon_ctx *src) { … } /** * damon_commit_ctx() - Commit parameters of a DAMON context to another. * @dst: The commit destination DAMON context. * @src: The commit source DAMON context. * * This function copies user-specified parameters from @src to @dst and update * the internal status and results accordingly. Users should use this function * for context-level parameters update of running context, instead of manual * in-place updates. * * This function should be called from parameters-update safe context, like * DAMON callbacks. */ int damon_commit_ctx(struct damon_ctx *dst, struct damon_ctx *src) { … } /** * damon_nr_running_ctxs() - Return number of currently running contexts. */ int damon_nr_running_ctxs(void) { … } /* Returns the size upper limit for each monitoring region */ static unsigned long damon_region_sz_limit(struct damon_ctx *ctx) { … } static int kdamond_fn(void *data); /* * __damon_start() - Starts monitoring with given context. * @ctx: monitoring context * * This function should be called while damon_lock is hold. * * Return: 0 on success, negative error code otherwise. */ static int __damon_start(struct damon_ctx *ctx) { … } /** * damon_start() - Starts the monitorings for a given group of contexts. * @ctxs: an array of the pointers for contexts to start monitoring * @nr_ctxs: size of @ctxs * @exclusive: exclusiveness of this contexts group * * This function starts a group of monitoring threads for a group of monitoring * contexts. One thread per each context is created and run in parallel. The * caller should handle synchronization between the threads by itself. If * @exclusive is true and a group of threads that created by other * 'damon_start()' call is currently running, this function does nothing but * returns -EBUSY. * * Return: 0 on success, negative error code otherwise. */ int damon_start(struct damon_ctx **ctxs, int nr_ctxs, bool exclusive) { … } /* * __damon_stop() - Stops monitoring of a given context. * @ctx: monitoring context * * Return: 0 on success, negative error code otherwise. */ static int __damon_stop(struct damon_ctx *ctx) { … } /** * damon_stop() - Stops the monitorings for a given group of contexts. * @ctxs: an array of the pointers for contexts to stop monitoring * @nr_ctxs: size of @ctxs * * Return: 0 on success, negative error code otherwise. */ int damon_stop(struct damon_ctx **ctxs, int nr_ctxs) { … } /* * Reset the aggregated monitoring results ('nr_accesses' of each region). */ static void kdamond_reset_aggregated(struct damon_ctx *c) { … } static void damon_split_region_at(struct damon_target *t, struct damon_region *r, unsigned long sz_r); static bool __damos_valid_target(struct damon_region *r, struct damos *s) { … } static bool damos_valid_target(struct damon_ctx *c, struct damon_target *t, struct damon_region *r, struct damos *s) { … } /* * damos_skip_charged_region() - Check if the given region or starting part of * it is already charged for the DAMOS quota. * @t: The target of the region. * @rp: The pointer to the region. * @s: The scheme to be applied. * * If a quota of a scheme has exceeded in a quota charge window, the scheme's * action would applied to only a part of the target access pattern fulfilling * regions. To avoid applying the scheme action to only already applied * regions, DAMON skips applying the scheme action to the regions that charged * in the previous charge window. * * This function checks if a given region should be skipped or not for the * reason. If only the starting part of the region has previously charged, * this function splits the region into two so that the second one covers the * area that not charged in the previous charge widnow and saves the second * region in *rp and returns false, so that the caller can apply DAMON action * to the second one. * * Return: true if the region should be entirely skipped, false otherwise. */ static bool damos_skip_charged_region(struct damon_target *t, struct damon_region **rp, struct damos *s) { … } static void damos_update_stat(struct damos *s, unsigned long sz_tried, unsigned long sz_applied) { … } static bool __damos_filter_out(struct damon_ctx *ctx, struct damon_target *t, struct damon_region *r, struct damos_filter *filter) { … } static bool damos_filter_out(struct damon_ctx *ctx, struct damon_target *t, struct damon_region *r, struct damos *s) { … } static void damos_apply_scheme(struct damon_ctx *c, struct damon_target *t, struct damon_region *r, struct damos *s) { … } static void damon_do_apply_schemes(struct damon_ctx *c, struct damon_target *t, struct damon_region *r) { … } /* * damon_feed_loop_next_input() - get next input to achieve a target score. * @last_input The last input. * @score Current score that made with @last_input. * * Calculate next input to achieve the target score, based on the last input * and current score. Assuming the input and the score are positively * proportional, calculate how much compensation should be added to or * subtracted from the last input as a proportion of the last input. Avoid * next input always being zero by setting it non-zero always. In short form * (assuming support of float and signed calculations), the algorithm is as * below. * * next_input = max(last_input * ((goal - current) / goal + 1), 1) * * For simple implementation, we assume the target score is always 10,000. The * caller should adjust @score for this. * * Returns next input that assumed to achieve the target score. */ static unsigned long damon_feed_loop_next_input(unsigned long last_input, unsigned long score) { … } #ifdef CONFIG_PSI static u64 damos_get_some_mem_psi_total(void) { … } #else /* CONFIG_PSI */ static inline u64 damos_get_some_mem_psi_total(void) { return 0; }; #endif /* CONFIG_PSI */ static void damos_set_quota_goal_current_value(struct damos_quota_goal *goal) { … } /* Return the highest score since it makes schemes least aggressive */ static unsigned long damos_quota_score(struct damos_quota *quota) { … } /* * Called only if quota->ms, or quota->sz are set, or quota->goals is not empty */ static void damos_set_effective_quota(struct damos_quota *quota) { … } static void damos_adjust_quota(struct damon_ctx *c, struct damos *s) { … } static void kdamond_apply_schemes(struct damon_ctx *c) { … } /* * Merge two adjacent regions into one region */ static void damon_merge_two_regions(struct damon_target *t, struct damon_region *l, struct damon_region *r) { … } /* * Merge adjacent regions having similar access frequencies * * t target affected by this merge operation * thres '->nr_accesses' diff threshold for the merge * sz_limit size upper limit of each region */ static void damon_merge_regions_of(struct damon_target *t, unsigned int thres, unsigned long sz_limit) { … } /* * Merge adjacent regions having similar access frequencies * * threshold '->nr_accesses' diff threshold for the merge * sz_limit size upper limit of each region * * This function merges monitoring target regions which are adjacent and their * access frequencies are similar. This is for minimizing the monitoring * overhead under the dynamically changeable access pattern. If a merge was * unnecessarily made, later 'kdamond_split_regions()' will revert it. * * The total number of regions could be higher than the user-defined limit, * max_nr_regions for some cases. For example, the user can update * max_nr_regions to a number that lower than the current number of regions * while DAMON is running. For such a case, repeat merging until the limit is * met while increasing @threshold up to possible maximum level. */ static void kdamond_merge_regions(struct damon_ctx *c, unsigned int threshold, unsigned long sz_limit) { … } /* * Split a region in two * * r the region to be split * sz_r size of the first sub-region that will be made */ static void damon_split_region_at(struct damon_target *t, struct damon_region *r, unsigned long sz_r) { … } /* Split every region in the given target into 'nr_subs' regions */ static void damon_split_regions_of(struct damon_target *t, int nr_subs) { … } /* * Split every target region into randomly-sized small regions * * This function splits every target region into random-sized small regions if * current total number of the regions is equal or smaller than half of the * user-specified maximum number of regions. This is for maximizing the * monitoring accuracy under the dynamically changeable access patterns. If a * split was unnecessarily made, later 'kdamond_merge_regions()' will revert * it. */ static void kdamond_split_regions(struct damon_ctx *ctx) { … } /* * Check whether current monitoring should be stopped * * The monitoring is stopped when either the user requested to stop, or all * monitoring targets are invalid. * * Returns true if need to stop current monitoring. */ static bool kdamond_need_stop(struct damon_ctx *ctx) { … } static int damos_get_wmark_metric_value(enum damos_wmark_metric metric, unsigned long *metric_value) { … } /* * Returns zero if the scheme is active. Else, returns time to wait for next * watermark check in micro-seconds. */ static unsigned long damos_wmark_wait_us(struct damos *scheme) { … } static void kdamond_usleep(unsigned long usecs) { … } /* Returns negative error code if it's not activated but should return */ static int kdamond_wait_activation(struct damon_ctx *ctx) { … } static void kdamond_init_intervals_sis(struct damon_ctx *ctx) { … } /* * The monitoring daemon that runs as a kernel thread */ static int kdamond_fn(void *data) { … } /* * struct damon_system_ram_region - System RAM resource address region of * [@start, @end). * @start: Start address of the region (inclusive). * @end: End address of the region (exclusive). */ struct damon_system_ram_region { … }; static int walk_system_ram(struct resource *res, void *arg) { … } /* * Find biggest 'System RAM' resource and store its start and end address in * @start and @end, respectively. If no System RAM is found, returns false. */ static bool damon_find_biggest_system_ram(unsigned long *start, unsigned long *end) { … } /** * damon_set_region_biggest_system_ram_default() - Set the region of the given * monitoring target as requested, or biggest 'System RAM'. * @t: The monitoring target to set the region. * @start: The pointer to the start address of the region. * @end: The pointer to the end address of the region. * * This function sets the region of @t as requested by @start and @end. If the * values of @start and @end are zero, however, this function finds the biggest * 'System RAM' resource and sets the region to cover the resource. In the * latter case, this function saves the start and end addresses of the resource * in @start and @end, respectively. * * Return: 0 on success, negative error code otherwise. */ int damon_set_region_biggest_system_ram_default(struct damon_target *t, unsigned long *start, unsigned long *end) { … } /* * damon_moving_sum() - Calculate an inferred moving sum value. * @mvsum: Inferred sum of the last @len_window values. * @nomvsum: Non-moving sum of the last discrete @len_window window values. * @len_window: The number of last values to take care of. * @new_value: New value that will be added to the pseudo moving sum. * * Moving sum (moving average * window size) is good for handling noise, but * the cost of keeping past values can be high for arbitrary window size. This * function implements a lightweight pseudo moving sum function that doesn't * keep the past window values. * * It simply assumes there was no noise in the past, and get the no-noise * assumed past value to drop from @nomvsum and @len_window. @nomvsum is a * non-moving sum of the last window. For example, if @len_window is 10 and we * have 25 values, @nomvsum is the sum of the 11th to 20th values of the 25 * values. Hence, this function simply drops @nomvsum / @len_window from * given @mvsum and add @new_value. * * For example, if @len_window is 10 and @nomvsum is 50, the last 10 values for * the last window could be vary, e.g., 0, 10, 0, 10, 0, 10, 0, 0, 0, 20. For * calculating next moving sum with a new value, we should drop 0 from 50 and * add the new value. However, this function assumes it got value 5 for each * of the last ten times. Based on the assumption, when the next value is * measured, it drops the assumed past value, 5 from the current sum, and add * the new value to get the updated pseduo-moving average. * * This means the value could have errors, but the errors will be disappeared * for every @len_window aligned calls. For example, if @len_window is 10, the * pseudo moving sum with 11th value to 19th value would have an error. But * the sum with 20th value will not have the error. * * Return: Pseudo-moving average after getting the @new_value. */ static unsigned int damon_moving_sum(unsigned int mvsum, unsigned int nomvsum, unsigned int len_window, unsigned int new_value) { … } /** * damon_update_region_access_rate() - Update the access rate of a region. * @r: The DAMON region to update for its access check result. * @accessed: Whether the region has accessed during last sampling interval. * @attrs: The damon_attrs of the DAMON context. * * Update the access rate of a region with the region's last sampling interval * access check result. * * Usually this will be called by &damon_operations->check_accesses callback. */ void damon_update_region_access_rate(struct damon_region *r, bool accessed, struct damon_attrs *attrs) { … } static int __init damon_init(void) { … } subsys_initcall(damon_init); #include "core-test.h"
Codebase Browser
linux