[PATCH v2 5/5] nilfs-utils: add support for greedy/cost-benefit policies

[Andreas Rohner <andreas.rohner-hi6Y0CQ0nG0@public.gmane.org>]

This patch implements the cost-benefit and greedy GC policies. These are
well known policies for log-structured file systems [1].

* Greedy:
  Select the segments with the most reclaimable space.
* Cost-Benefit [1]:
  Perform a cost-benefit analysis, whereby the reclaimable space
  gained is weighed against the cost of collecting the segment.

Since especially cost-benefit needs more information than is available
in nilfs_suinfo, a few extra parameters are added to the policy callback
function prototype. The flag p_comparison is added to indicate how the
importance values should be interpreted. For example for the timestamp
policy smaller values mean older timestamps, which is better. For greedy
and cost-benefit on the other hand, higher values are better.
nilfs_cleanerd_select_segments() was updated accordingly.

The threshold in nilfs_cleanerd_select_segments() can no longer be set
to sustat->ss_nongc_ctime on default, because the greedy/cost-benefit
policies do not return a timestamp, so their importance values cannot be
compared to each other. Instead segments that are younger than
sustat->ss_nongc_ctime are always excluded.

[1] Mendel Rosenblum and John K. Ousterhout. The design and implementa-
tion of a log-structured file system. ACM Trans. Comput. Syst.,
10(1):26–52, February 1992.

Signed-off-by: Andreas Rohner <andreas.rohner-hi6Y0CQ0nG0@public.gmane.org>
---
 sbin/cleanerd/cldconfig.c | 79 +++++++++++++++++++++++++++++++++++++++++++++--
 sbin/cleanerd/cldconfig.h | 22 +++++++++----
 sbin/cleanerd/cleanerd.c  | 43 ++++++++++++++++++++------
 3 files changed, 126 insertions(+), 18 deletions(-)

diff --git a/sbin/cleanerd/cldconfig.c b/sbin/cleanerd/cldconfig.c
index c8b197b..68090e9 100644
--- a/sbin/cleanerd/cldconfig.c
+++ b/sbin/cleanerd/cldconfig.c
@@ -380,7 +380,9 @@ nilfs_cldconfig_handle_clean_check_interval(struct nilfs_cldconfig *config,
 }
 
 static unsigned long long
-nilfs_cldconfig_selection_policy_timestamp(const struct nilfs_suinfo *si)
+nilfs_cldconfig_selection_policy_timestamp(const struct nilfs_suinfo *si,
+					   const struct nilfs_sustat *sustat,
+					   __u64 prottime)
 {
 	return si->sui_lastmod;
 }
@@ -392,13 +394,84 @@ nilfs_cldconfig_handle_selection_policy_timestamp(struct nilfs_cldconfig *config
 	config->cf_selection_policy.p_importance =
 		NILFS_CLDCONFIG_SELECTION_POLICY_IMPORTANCE;
 	config->cf_selection_policy.p_threshold =
-		NILFS_CLDCONFIG_SELECTION_POLICY_THRESHOLD;
+		NILFS_CLDCONFIG_SELECTION_POLICY_NO_THRESHOLD;
+	config->cf_selection_policy.p_comparison =
+		NILFS_CLDCONFIG_SELECTION_POLICY_SMALLER_IS_BETTER;
+	return 0;
+}
+
+static unsigned long long
+nilfs_cldconfig_selection_policy_greedy(const struct nilfs_suinfo *si,
+					const struct nilfs_sustat *sustat,
+					__u64 prottime)
+{
+	if (si->sui_nblocks < si->sui_nlive_blks ||
+	    si->sui_nlive_lastmod >= prottime)
+		return 0;
+
+	return si->sui_nblocks - si->sui_nlive_blks;
+}
+
+static int
+nilfs_cldconfig_handle_selection_policy_greedy(struct nilfs_cldconfig *config,
+					       char **tokens, size_t ntoks)
+{
+	config->cf_selection_policy.p_importance =
+		nilfs_cldconfig_selection_policy_greedy;
+	config->cf_selection_policy.p_threshold =
+		NILFS_CLDCONFIG_SELECTION_POLICY_NO_THRESHOLD;
+	config->cf_selection_policy.p_comparison =
+		NILFS_CLDCONFIG_SELECTION_POLICY_BIGGER_IS_BETTER;
+	return 0;
+}
+
+static unsigned long long
+nilfs_cldconfig_selection_policy_cost_benefit(const struct nilfs_suinfo *si,
+					      const struct nilfs_sustat *sustat,
+					      __u64 prottime)
+{
+	__u32 free_blocks, cleaning_cost;
+	unsigned long long age;
+
+	if (si->sui_nblocks < si->sui_nlive_blks ||
+	    sustat->ss_nongc_ctime < si->sui_lastmod ||
+	    si->sui_nlive_lastmod >= prottime)
+		return 0;
+
+	free_blocks = si->sui_nblocks - si->sui_nlive_blks;
+	/* read the whole segment + write the live blocks */
+	cleaning_cost = 2 * si->sui_nlive_blks;
+	/*
+	 * multiply by 1000 to convert age to milliseconds
+	 * (higher precision for division)
+	 */
+	age = (sustat->ss_nongc_ctime - si->sui_lastmod) * 1000;
+
+	if (cleaning_cost == 0)
+		cleaning_cost = 1;
+
+	return (age * free_blocks) / cleaning_cost;
+}
+
+static int
+nilfs_cldconfig_handle_selection_policy_cost_benefit(
+						struct nilfs_cldconfig *config,
+						char **tokens, size_t ntoks)
+{
+	config->cf_selection_policy.p_importance =
+		nilfs_cldconfig_selection_policy_cost_benefit;
+	config->cf_selection_policy.p_threshold =
+		NILFS_CLDCONFIG_SELECTION_POLICY_NO_THRESHOLD;
+	config->cf_selection_policy.p_comparison =
+		NILFS_CLDCONFIG_SELECTION_POLICY_BIGGER_IS_BETTER;
 	return 0;
 }
 
 static const struct nilfs_cldconfig_polhandle
 nilfs_cldconfig_polhandle_table[] = {
 	{"timestamp",	nilfs_cldconfig_handle_selection_policy_timestamp},
+	{"greedy",	nilfs_cldconfig_handle_selection_policy_greedy},
+	{"cost-benefit", nilfs_cldconfig_handle_selection_policy_cost_benefit},
 };
 
 #define NILFS_CLDCONFIG_NPOLHANDLES			\
@@ -690,6 +763,8 @@ static void nilfs_cldconfig_set_default(struct nilfs_cldconfig *config,
 		NILFS_CLDCONFIG_SELECTION_POLICY_IMPORTANCE;
 	config->cf_selection_policy.p_threshold =
 		NILFS_CLDCONFIG_SELECTION_POLICY_THRESHOLD;
+	config->cf_selection_policy.p_comparison =
+		NILFS_CLDCONFIG_SELECTION_POLICY_COMPARISON;
 	config->cf_protection_period.tv_sec = NILFS_CLDCONFIG_PROTECTION_PERIOD;
 	config->cf_protection_period.tv_usec = 0;
 
diff --git a/sbin/cleanerd/cldconfig.h b/sbin/cleanerd/cldconfig.h
index 2a0af5f..3c9f5e6 100644
--- a/sbin/cleanerd/cldconfig.h
+++ b/sbin/cleanerd/cldconfig.h
@@ -30,16 +30,22 @@
 #include <sys/time.h>
 #include <syslog.h>
 
+struct nilfs;
+struct nilfs_sustat;
 struct nilfs_suinfo;
 
 /**
  * struct nilfs_selection_policy -
- * @p_importance:
- * @p_threshold:
+ * @p_importance: function to calculate the importance for the policy
+ * @p_threshold: segments with lower/higher importance are ignored
+ * @p_comparison: flag that indicates how to sort the importance
  */
 struct nilfs_selection_policy {
-	unsigned long long (*p_importance)(const struct nilfs_suinfo *);
+	unsigned long long (*p_importance)(const struct nilfs_suinfo *,
+					   const struct nilfs_sustat *,
+					   __u64);
 	unsigned long long p_threshold;
+	int p_comparison;
 };
 
 /**
@@ -111,9 +117,15 @@ struct nilfs_cldconfig {
 	unsigned long cf_mc_min_reclaimable_blocks;
 };
 
+#define NILFS_CLDCONFIG_SELECTION_POLICY_SMALLER_IS_BETTER	0
+#define NILFS_CLDCONFIG_SELECTION_POLICY_BIGGER_IS_BETTER	1
+#define NILFS_CLDCONFIG_SELECTION_POLICY_NO_THRESHOLD	0
 #define NILFS_CLDCONFIG_SELECTION_POLICY_IMPORTANCE	\
 			nilfs_cldconfig_selection_policy_timestamp
-#define NILFS_CLDCONFIG_SELECTION_POLICY_THRESHOLD	0
+#define NILFS_CLDCONFIG_SELECTION_POLICY_THRESHOLD	\
+			NILFS_CLDCONFIG_SELECTION_POLICY_NO_THRESHOLD
+#define NILFS_CLDCONFIG_SELECTION_POLICY_COMPARISON	\
+			NILFS_CLDCONFIG_SELECTION_POLICY_SMALLER_IS_BETTER
 #define NILFS_CLDCONFIG_PROTECTION_PERIOD		3600
 #define NILFS_CLDCONFIG_MIN_CLEAN_SEGMENTS		10
 #define NILFS_CLDCONFIG_MIN_CLEAN_SEGMENTS_UNIT		NILFS_SIZE_UNIT_PERCENT
@@ -135,8 +147,6 @@ struct nilfs_cldconfig {
 
 #define NILFS_CLDCONFIG_NSEGMENTS_PER_CLEAN_MAX	32
 
-struct nilfs;
-
 int nilfs_cldconfig_read(struct nilfs_cldconfig *config, const char *path,
 			 struct nilfs *nilfs);
 
diff --git a/sbin/cleanerd/cleanerd.c b/sbin/cleanerd/cleanerd.c
index d37bd5c..e0741f1 100644
--- a/sbin/cleanerd/cleanerd.c
+++ b/sbin/cleanerd/cleanerd.c
@@ -417,7 +417,7 @@ static void nilfs_cleanerd_destroy(struct nilfs_cleanerd *cleanerd)
 	free(cleanerd);
 }
 
-static int nilfs_comp_segimp(const void *elem1, const void *elem2)
+static int nilfs_comp_segimp_asc(const void *elem1, const void *elem2)
 {
 	const struct nilfs_segimp *segimp1 = elem1, *segimp2 = elem2;
 
@@ -429,6 +429,18 @@ static int nilfs_comp_segimp(const void *elem1, const void *elem2)
 	return (segimp1->si_segnum < segimp2->si_segnum) ? -1 : 1;
 }
 
+static int nilfs_comp_segimp_desc(const void *elem1, const void *elem2)
+{
+	const struct nilfs_segimp *segimp1 = elem1, *segimp2 = elem2;
+
+	if (segimp1->si_importance > segimp2->si_importance)
+		return -1;
+	else if (segimp1->si_importance < segimp2->si_importance)
+		return 1;
+
+	return (segimp1->si_segnum < segimp2->si_segnum) ? -1 : 1;
+}
+
 static int nilfs_cleanerd_automatic_suspend(struct nilfs_cleanerd *cleanerd)
 {
 	return cleanerd->config.cf_min_clean_segments > 0;
@@ -580,7 +592,7 @@ nilfs_cleanerd_select_segments(struct nilfs_cleanerd *cleanerd,
 	size_t count, nsegs;
 	ssize_t nssegs, n;
 	unsigned long long imp, thr;
-	int i;
+	int i, sib;
 
 	nsegs = nilfs_cleanerd_ncleansegs(cleanerd);
 	nilfs = cleanerd->nilfs;
@@ -600,11 +612,17 @@ nilfs_cleanerd_select_segments(struct nilfs_cleanerd *cleanerd,
 	prottime = tv2.tv_sec;
 	oldest = tv.tv_sec;
 
-	/* The segments that have larger importance than thr are not
+	/*
+	 * sufile extension fields may not be initialized by
+	 * nilfs_get_suinfo()
+	 */
+	memset(si, 0, sizeof(si));
+
+	/* The segments that have larger/smaller importance than thr are not
 	 * selected. */
-	thr = (config->cf_selection_policy.p_threshold != 0) ?
-		config->cf_selection_policy.p_threshold :
-		sustat->ss_nongc_ctime;
+	thr = config->cf_selection_policy.p_threshold;
+	sib = config->cf_selection_policy.p_comparison ==
+			NILFS_CLDCONFIG_SELECTION_POLICY_SMALLER_IS_BETTER;
 
 	for (segnum = 0; segnum < sustat->ss_nsegs; segnum += n) {
 		count = min_t(__u64, sustat->ss_nsegs - segnum,
@@ -615,11 +633,13 @@ nilfs_cleanerd_select_segments(struct nilfs_cleanerd *cleanerd,
 			goto out;
 		}
 		for (i = 0; i < n; i++) {
-			if (!nilfs_suinfo_reclaimable(&si[i]))
+			if (!nilfs_suinfo_reclaimable(&si[i]) ||
+				si[i].sui_lastmod >= sustat->ss_nongc_ctime)
 				continue;
 
-			imp = config->cf_selection_policy.p_importance(&si[i]);
-			if (imp < thr) {
+			imp = config->cf_selection_policy.p_importance(&si[i],
+					sustat, prottime);
+			if (!thr || (sib && imp < thr) || (!sib && imp > thr)) {
 				if (si[i].sui_lastmod < oldest)
 					oldest = si[i].sui_lastmod;
 				if (si[i].sui_lastmod < prottime) {
@@ -642,7 +662,10 @@ nilfs_cleanerd_select_segments(struct nilfs_cleanerd *cleanerd,
 			break;
 		}
 	}
-	nilfs_vector_sort(smv, nilfs_comp_segimp);
+	if (sib)
+		nilfs_vector_sort(smv, nilfs_comp_segimp_asc);
+	else
+		nilfs_vector_sort(smv, nilfs_comp_segimp_desc);
 
 	nssegs = (nilfs_vector_get_size(smv) < nsegs) ?
 		nilfs_vector_get_size(smv) : nsegs;
-- 
2.3.7

--
To unsubscribe from this list: send the line "unsubscribe linux-nilfs" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html