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@xxxxxxx>
---
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@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
