@@ -65,6 +65,7 @@ struct damon_task {
* @sample_interval: The time between access samplings.
* @aggr_interval: The time between monitor results aggregations.
* @min_nr_regions: The number of initial monitoring regions.
+ * @max_nr_regions: The maximum number of monitoring regions.
*
* For each @sample_interval, DAMON checks whether each region is accessed or
* not. It aggregates and keeps the access information (number of accesses to
@@ -115,6 +116,7 @@ struct damon_ctx {
unsigned long sample_interval;
unsigned long aggr_interval;
unsigned long min_nr_regions;
+ unsigned long max_nr_regions;
struct timespec64 last_aggregation;
@@ -133,8 +135,9 @@ struct damon_ctx {
};
int damon_set_pids(struct damon_ctx *ctx, int *pids, ssize_t nr_pids);
-int damon_set_attrs(struct damon_ctx *ctx, unsigned long sample_int,
- unsigned long aggr_int, unsigned long min_nr_reg);
+int damon_set_attrs(struct damon_ctx *ctx,
+ unsigned long sample_int, unsigned long aggr_int,
+ unsigned long min_nr_reg, unsigned long max_nr_reg);
int damon_start(struct damon_ctx *ctx);
int damon_stop(struct damon_ctx *ctx);
@@ -176,6 +176,26 @@ static unsigned int nr_damon_regions(struct damon_task *t)
return nr_regions;
}
+/* Returns the size upper limit for each monitoring region */
+static unsigned long damon_region_sz_limit(struct damon_ctx *ctx)
+{
+ struct damon_task *t;
+ struct damon_region *r;
+ unsigned long sz = 0;
+
+ damon_for_each_task(t, ctx) {
+ damon_for_each_region(r, t)
+ sz += r->ar.end - r->ar.start;
+ }
+
+ if (ctx->min_nr_regions)
+ sz /= ctx->min_nr_regions;
+ if (sz < MIN_REGION)
+ sz = MIN_REGION;
+
+ return sz;
+}
+
/*
* Functions for DAMON core logics and features
*/
@@ -226,6 +246,145 @@ static void kdamond_reset_aggregated(struct damon_ctx *c)
}
}
+#define sz_damon_region(r) (r->ar.end - r->ar.start)
+
+/*
+ * Merge two adjacent regions into one region
+ */
+static void damon_merge_two_regions(struct damon_region *l,
+ struct damon_region *r)
+{
+ l->nr_accesses = (l->nr_accesses * sz_damon_region(l) +
+ r->nr_accesses * sz_damon_region(r)) /
+ (sz_damon_region(l) + sz_damon_region(r));
+ l->ar.end = r->ar.end;
+ damon_destroy_region(r);
+}
+
+#define diff_of(a, b) (a > b ? a - b : b - a)
+
+/*
+ * Merge adjacent regions having similar access frequencies
+ *
+ * t task affected by 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_task *t, unsigned int thres,
+ unsigned long sz_limit)
+{
+ struct damon_region *r, *prev = NULL, *next;
+
+ damon_for_each_region_safe(r, next, t) {
+ if (prev && prev->ar.end == r->ar.start &&
+ diff_of(prev->nr_accesses, r->nr_accesses) <= thres &&
+ sz_damon_region(prev) + sz_damon_region(r) <= sz_limit)
+ damon_merge_two_regions(prev, r);
+ else
+ prev = r;
+ }
+}
+
+/*
+ * 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.
+ */
+static void kdamond_merge_regions(struct damon_ctx *c, unsigned int threshold,
+ unsigned long sz_limit)
+{
+ struct damon_task *t;
+
+ damon_for_each_task(t, c)
+ damon_merge_regions_of(t, threshold, 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_ctx *ctx,
+ struct damon_region *r, unsigned long sz_r)
+{
+ struct damon_region *new;
+
+ new = damon_new_region(ctx, r->ar.start + sz_r, r->ar.end);
+ r->ar.end = new->ar.start;
+
+ damon_insert_region(new, r, damon_next_region(r));
+}
+
+/* Split every region in the given task into 'nr_subs' regions */
+static void damon_split_regions_of(struct damon_ctx *ctx,
+ struct damon_task *t, int nr_subs)
+{
+ struct damon_region *r, *next;
+ unsigned long sz_region, sz_sub = 0;
+ int i;
+
+ damon_for_each_region_safe(r, next, t) {
+ sz_region = r->ar.end - r->ar.start;
+
+ for (i = 0; i < nr_subs - 1 &&
+ sz_region > 2 * MIN_REGION; i++) {
+ /*
+ * Randomly select size of left sub-region to be at
+ * least 10 percent and at most 90% of original region
+ */
+ sz_sub = ALIGN_DOWN(damon_rand(1, 10) *
+ sz_region / 10, MIN_REGION);
+ /* Do not allow blank region */
+ if (sz_sub == 0 || sz_sub >= sz_region)
+ continue;
+
+ damon_split_region_at(ctx, r, sz_sub);
+ sz_region = sz_sub;
+ }
+ }
+}
+
+/*
+ * splits every target region into two randomly-sized regions
+ *
+ * This function splits every target region into two random-sized 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)
+{
+ struct damon_task *t;
+ unsigned int nr_regions = 0;
+ static unsigned int last_nr_regions;
+ int nr_subregions = 2;
+
+ damon_for_each_task(t, ctx)
+ nr_regions += nr_damon_regions(t);
+
+ if (nr_regions > ctx->max_nr_regions / 2)
+ return;
+
+ /* If number of regions is not changed, we are maybe in corner case */
+ if (last_nr_regions == nr_regions &&
+ nr_regions < ctx->max_nr_regions / 3)
+ nr_subregions = 3;
+
+ damon_for_each_task(t, ctx)
+ damon_split_regions_of(ctx, t, nr_subregions);
+
+ last_nr_regions = nr_regions;
+}
+
/*
* Check whether current monitoring should be stopped
*
@@ -269,10 +428,14 @@ static int kdamond_fn(void *data)
struct damon_ctx *ctx = (struct damon_ctx *)data;
struct damon_task *t;
struct damon_region *r, *next;
+ unsigned int max_nr_accesses = 0;
+ unsigned long sz_limit = 0;
pr_info("kdamond (%d) starts\n", ctx->kdamond->pid);
if (ctx->init_target_regions)
ctx->init_target_regions(ctx);
+ sz_limit = damon_region_sz_limit(ctx);
+
while (!kdamond_need_stop(ctx)) {
if (ctx->prepare_access_checks)
ctx->prepare_access_checks(ctx);
@@ -282,14 +445,16 @@ static int kdamond_fn(void *data)
usleep_range(ctx->sample_interval, ctx->sample_interval + 1);
if (ctx->check_accesses)
- ctx->check_accesses(ctx);
+ max_nr_accesses = ctx->check_accesses(ctx);
if (kdamond_aggregate_interval_passed(ctx)) {
if (ctx->aggregate_cb)
ctx->aggregate_cb(ctx);
+ kdamond_merge_regions(ctx, max_nr_accesses / 10,
+ sz_limit);
kdamond_reset_aggregated(ctx);
+ kdamond_split_regions(ctx);
}
-
}
damon_for_each_task(t, ctx) {
damon_for_each_region_safe(r, next, t)
@@ -399,24 +564,32 @@ int damon_set_pids(struct damon_ctx *ctx, int *pids, ssize_t nr_pids)
* @sample_int: time interval between samplings
* @aggr_int: time interval between aggregations
* @min_nr_reg: minimal number of regions
+ * @max_nr_reg: maximum number of regions
*
* This function should not be called while the kdamond is running.
* Every time interval is in micro-seconds.
*
* Return: 0 on success, negative error code otherwise.
*/
-int damon_set_attrs(struct damon_ctx *ctx, unsigned long sample_int,
- unsigned long aggr_int, unsigned long min_nr_reg)
+int damon_set_attrs(struct damon_ctx *ctx,
+ unsigned long sample_int, unsigned long aggr_int,
+ unsigned long min_nr_reg, unsigned long max_nr_reg)
{
if (min_nr_reg < 3) {
pr_err("min_nr_regions (%lu) must be at least 3\n",
min_nr_reg);
return -EINVAL;
}
+ if (min_nr_reg > max_nr_reg) {
+ pr_err("invalid nr_regions. min (%lu) > max (%lu)\n",
+ min_nr_reg, max_nr_reg);
+ return -EINVAL;
+ }
ctx->sample_interval = sample_int;
ctx->aggr_interval = aggr_int;
ctx->min_nr_regions = min_nr_reg;
+ ctx->max_nr_regions = max_nr_reg;
return 0;
}