@@ -73,6 +73,7 @@ static unsigned long aggr_interval = 100 * 1000;
static struct timespec64 last_aggregate_time;
static unsigned long min_nr_regions = 10;
+static unsigned long max_nr_regions = 1000;
/* result buffer */
#define DAMON_LEN_RBUF (1024 * 1024 * 4)
@@ -398,7 +399,12 @@ static int damon_three_regions_of(struct damon_task *t,
* regions is wasteful. That said, because we can deal with small noises,
* tracking every mapping is not strictly required but could even incur a high
* overhead if the mapping frequently changes or the number of mappings is
- * high.
+ * high. The adaptive regions adjustment mechanism will further help to deal
+ * with the noises by simply identifying the unmapped areas as a region that
+ * has no access. Moreover, applying the real mappings that would have many
+ * unmapped areas inside will make the adaptive mechanism quite complex. That
+ * said, too huge unmapped areas inside the monitoring target should be removed
+ * to not take the time for the adaptive mechanism.
*
* For the reason, we convert the complex mappings to three distinct regions
* that cover every mapped areas of the address space. Also the two gaps
@@ -618,6 +624,122 @@ static void kdamond_flush_aggregated(void)
}
}
+#define sz_damon_region(r) (r->vm_end - r->vm_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->vm_end = r->vm_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 that merge operation will make change
+ * thres merge regions having '->nr_accesses' diff smaller than this
+ */
+static void damon_merge_regions_of(struct damon_task *t, unsigned int thres)
+{
+ struct damon_region *r, *prev = NULL, *next;
+
+ damon_for_each_region_safe(r, next, t) {
+ if (!prev || prev->vm_end != r->vm_start)
+ goto next;
+ if (diff_of(prev->nr_accesses, r->nr_accesses) > thres)
+ goto next;
+ damon_merge_two_regions(prev, r);
+ continue;
+next:
+ prev = r;
+ }
+}
+
+/*
+ * Merge adjacent regions having similar access frequencies
+ *
+ * threshold merge regions havind nr_accesses diff larger than this
+ *
+ * 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(unsigned int threshold)
+{
+ struct damon_task *t;
+
+ damon_for_each_task(t)
+ damon_merge_regions_of(t, threshold);
+}
+
+/*
+ * Split a region into two small regions
+ *
+ * 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_region *r, unsigned long sz_r)
+{
+ struct damon_region *new;
+
+ new = damon_new_region(r->vm_start + sz_r, r->vm_end);
+ r->vm_end = new->vm_start;
+
+ damon_add_region(new, r, damon_next_region(r));
+}
+
+static void damon_split_regions_of(struct damon_task *t)
+{
+ struct damon_region *r, *next;
+ unsigned long sz_left_region;
+
+ damon_for_each_region_safe(r, next, t) {
+ /*
+ * Randomly select size of left sub-region to be at least
+ * 10 percent and at most 90% of original region
+ */
+ sz_left_region = (prandom_u32_state(&rndseed) % 9 + 1) *
+ (r->vm_end - r->vm_start) / 10;
+ /* Do not allow blank region */
+ if (sz_left_region == 0)
+ continue;
+ damon_split_region_at(r, sz_left_region);
+ }
+}
+
+/*
+ * splits every target regions into two randomly-sized regions
+ *
+ * This function splits every target regions into two random-sized regions if
+ * current total number of the regions is smaller than the 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(void)
+{
+ struct damon_task *t;
+ unsigned int nr_regions = 0;
+
+ damon_for_each_task(t)
+ nr_regions += nr_damon_regions(t);
+ if (nr_regions > max_nr_regions / 2)
+ return;
+
+ damon_for_each_task(t)
+ damon_split_regions_of(t);
+}
+
/*
* Check whether current monitoring should be stopped
*
@@ -657,21 +779,29 @@ static int kdamond_fn(void *data)
struct damon_task *t;
struct damon_region *r, *next;
struct mm_struct *mm;
+ unsigned long max_nr_accesses;
pr_info("kdamond (%d) starts\n", kdamond->pid);
kdamond_init_regions();
while (!kdamond_need_stop()) {
+ max_nr_accesses = 0;
damon_for_each_task(t) {
mm = damon_get_mm(t);
if (!mm)
continue;
- damon_for_each_region(r, t)
+ damon_for_each_region(r, t) {
kdamond_check_access(mm, r);
+ if (r->nr_accesses > max_nr_accesses)
+ max_nr_accesses = r->nr_accesses;
+ }
mmput(mm);
}
- if (kdamond_aggregate_interval_passed())
+ if (kdamond_aggregate_interval_passed()) {
+ kdamond_merge_regions(max_nr_accesses / 10);
kdamond_flush_aggregated();
+ kdamond_split_regions();
+ }
usleep_range(sample_interval, sample_interval + 1);
}
@@ -780,6 +910,7 @@ static long damon_set_pids(unsigned long *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
* path_to_rfile path to the monitor result files
*
* This function should not be called while the kdamond is running.
@@ -787,8 +918,10 @@ static long damon_set_pids(unsigned long *pids, ssize_t nr_pids)
*
* Returns 0 on success, negative error code otherwise.
*/
-static long damon_set_attrs(unsigned long sample_int, unsigned long aggr_int,
- unsigned long min_nr_reg, char *path_to_rfile)
+static long damon_set_attrs(unsigned long sample_int,
+ unsigned long aggr_int,
+ unsigned long min_nr_reg, unsigned long max_nr_reg,
+ char *path_to_rfile)
{
if (strnlen(path_to_rfile, LEN_RES_FILE_PATH) >= LEN_RES_FILE_PATH) {
pr_err("too long (>%d) result file path %s\n",
@@ -800,10 +933,16 @@ static long damon_set_attrs(unsigned long sample_int, unsigned long aggr_int,
min_nr_reg);
return -EINVAL;
}
+ if (min_nr_reg >= max_nr_regions) {
+ pr_err("invalid nr_regions. min (%lu) >= max (%lu)\n",
+ min_nr_reg, max_nr_reg);
+ return -EINVAL;
+ }
sample_interval = sample_int;
aggr_interval = aggr_int;
min_nr_regions = min_nr_reg;
+ max_nr_regions = max_nr_reg;
strncpy(rfile_path, path_to_rfile, LEN_RES_FILE_PATH);
return 0;
}