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 free space.
* Cost-Benefit:
Perform a cost-benefit analysis, whereby the free space gained is
weighed against the cost of collecting the segment.
Since especially cost-benefit needed more information than was available
in nilfs_suinfo, a few extra parameters were added to the policy
callback function prototype. The policy threshold was removed, since it
served no real purpose. The flag p_comparison was 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.
[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>
---
include/nilfs2_fs.h | 9 ++++-
sbin/cleanerd/cldconfig.c | 100 +++++++++++++++++++++++++++++++++++++++++++---
sbin/cleanerd/cldconfig.h | 18 +++++----
sbin/cleanerd/cleanerd.c | 56 ++++++++++++++++----------
4 files changed, 149 insertions(+), 34 deletions(-)
diff --git a/include/nilfs2_fs.h b/include/nilfs2_fs.h
index a16ad4c..967c2af 100644
--- a/include/nilfs2_fs.h
+++ b/include/nilfs2_fs.h
@@ -483,7 +483,7 @@ struct nilfs_dat_entry {
__le64 de_blocknr;
__le64 de_start;
__le64 de_end;
- __le64 de_rsv;
+ __le64 de_ss;
};
/**
@@ -612,11 +612,13 @@ struct nilfs_cpfile_header {
* @su_lastmod: last modified timestamp
* @su_nblocks: number of blocks in segment
* @su_flags: flags
+ * @su_lastdec: last decrement of su_nblocks timestamp
*/
struct nilfs_segment_usage {
__le64 su_lastmod;
__le32 su_nblocks;
__le32 su_flags;
+ __le64 su_lastdec;
};
/* segment usage flag */
@@ -659,6 +661,7 @@ nilfs_segment_usage_set_clean(struct nilfs_segment_usage *su)
su->su_lastmod = cpu_to_le64(0);
su->su_nblocks = cpu_to_le32(0);
su->su_flags = cpu_to_le32(0);
+ su->su_lastdec = cpu_to_le64(0);
}
static inline int
@@ -690,11 +693,13 @@ struct nilfs_sufile_header {
* @sui_lastmod: timestamp of last modification
* @sui_nblocks: number of written blocks in segment
* @sui_flags: segment usage flags
+ * @sui_lastdec: last decrement of sui_nblocks timestamp
*/
struct nilfs_suinfo {
__u64 sui_lastmod;
__u32 sui_nblocks;
__u32 sui_flags;
+ __u64 sui_lastdec;
};
#define NILFS_SUINFO_FNS(flag, name) \
@@ -732,6 +737,7 @@ enum {
NILFS_SUINFO_UPDATE_LASTMOD,
NILFS_SUINFO_UPDATE_NBLOCKS,
NILFS_SUINFO_UPDATE_FLAGS,
+ NILFS_SUINFO_UPDATE_LASTDEC,
__NR_NILFS_SUINFO_UPDATE_FIELDS,
};
@@ -755,6 +761,7 @@ nilfs_suinfo_update_##name(const struct nilfs_suinfo_update *sup) \
NILFS_SUINFO_UPDATE_FNS(LASTMOD, lastmod)
NILFS_SUINFO_UPDATE_FNS(NBLOCKS, nblocks)
NILFS_SUINFO_UPDATE_FNS(FLAGS, flags)
+NILFS_SUINFO_UPDATE_FNS(LASTDEC, lastdec)
enum {
NILFS_CHECKPOINT,
diff --git a/sbin/cleanerd/cldconfig.c b/sbin/cleanerd/cldconfig.c
index c8b197b..ade974a 100644
--- a/sbin/cleanerd/cldconfig.c
+++ b/sbin/cleanerd/cldconfig.c
@@ -380,7 +380,10 @@ 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(struct nilfs *nilfs,
+ const struct nilfs_sustat *sustat,
+ const struct nilfs_suinfo *si,
+ __u64 prottime)
{
return si->sui_lastmod;
}
@@ -391,14 +394,101 @@ 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;
+ config->cf_selection_policy.p_comparison =
+ NILFS_CLDCONFIG_SELECTION_POLICY_SMALLER_IS_BETTER;
+ return 0;
+}
+
+static unsigned long long
+nilfs_cldconfig_selection_policy_greedy(struct nilfs *nilfs,
+ const struct nilfs_sustat *sustat,
+ const struct nilfs_suinfo *si,
+ __u64 prottime)
+{
+ __u32 value, max_blocks = nilfs_get_blocks_per_segment(nilfs);
+
+ if (max_blocks < si->sui_nblocks)
+ return 0;
+
+ value = max_blocks - si->sui_nblocks;
+
+ /*
+ * the value of sui_nblocks is probably not accurate
+ * because blocks inside the protection period are not
+ * considered to be dead
+ */
+ if (si->sui_lastdec >= prottime)
+ value >>= 4;
+
+ return value;
+}
+
+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_comparison =
+ NILFS_CLDCONFIG_SELECTION_POLICY_BIGGER_IS_BETTER;
+ return 0;
+}
+
+static unsigned long long
+nilfs_cldconfig_selection_policy_cost_benefit(struct nilfs *nilfs,
+ const struct nilfs_sustat *sustat,
+ const struct nilfs_suinfo *si,
+ __u64 prottime)
+{
+ __u32 free_blocks, cleaning_cost;
+ unsigned long long value, age;
+
+ free_blocks = nilfs_get_blocks_per_segment(nilfs) - si->sui_nblocks;
+ /* read the whole segment + write the live blocks */
+ cleaning_cost = 2 * si->sui_nblocks;
+ /*
+ * multiply by 1000 to convert age to milliseconds
+ * (higher precision for division)
+ */
+ age = (sustat->ss_nongc_ctime - si->sui_lastmod) * 1000;
+
+ if (sustat->ss_nongc_ctime < si->sui_lastmod)
+ return 0;
+
+ if (cleaning_cost == 0)
+ cleaning_cost = 1;
+
+
+ value = (age * free_blocks) / cleaning_cost;
+
+ /*
+ * the value of sui_nblocks is probably not accurate
+ * because blocks inside the protection period are not
+ * considered to be dead
+ */
+ if (si->sui_lastdec >= prottime)
+ value >>= 4;
+
+ return value;
+}
+
+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_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 \
@@ -688,8 +778,8 @@ static void nilfs_cldconfig_set_default(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;
+ config->cf_selection_policy.p_comparison =
+ NILFS_CLDCONFIG_SELECTION_POLICY_SMALLER_IS_BETTER;
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 0a598d5..95d2fde 100644
--- a/sbin/cleanerd/cldconfig.h
+++ b/sbin/cleanerd/cldconfig.h
@@ -30,16 +30,21 @@
#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_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_threshold;
+ unsigned long long (*p_importance)(struct nilfs *nilfs,
+ const struct nilfs_sustat *sustat,
+ const struct nilfs_suinfo *,
+ __u64 prottime);
+ int p_comparison;
};
/**
@@ -113,7 +118,8 @@ struct nilfs_cldconfig {
#define NILFS_CLDCONFIG_SELECTION_POLICY_IMPORTANCE \
nilfs_cldconfig_selection_policy_timestamp
-#define NILFS_CLDCONFIG_SELECTION_POLICY_THRESHOLD 0
+#define NILFS_CLDCONFIG_SELECTION_POLICY_BIGGER_IS_BETTER 0
+#define NILFS_CLDCONFIG_SELECTION_POLICY_SMALLER_IS_BETTER 1
#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 +141,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 17de87b..8df3a07 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;
@@ -579,7 +591,7 @@ nilfs_cleanerd_select_segments(struct nilfs_cleanerd *cleanerd,
__u64 segnum;
size_t count, nsegs;
ssize_t nssegs, n;
- unsigned long long imp, thr;
+ unsigned long long imp;
int i;
nsegs = nilfs_cleanerd_ncleansegs(cleanerd);
@@ -600,11 +612,8 @@ 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
- * selected. */
- thr = (config->cf_selection_policy.p_threshold != 0) ?
- config->cf_selection_policy.p_threshold :
- sustat->ss_nongc_ctime;
+ /* sui_lastdec may not be set by nilfs_get_suinfo */
+ memset(si, 0, sizeof(si));
for (segnum = 0; segnum < sustat->ss_nsegs; segnum += n) {
count = min_t(__u64, sustat->ss_nsegs - segnum,
@@ -615,22 +624,23 @@ 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) {
- if (si[i].sui_lastmod < oldest)
- oldest = si[i].sui_lastmod;
- if (si[i].sui_lastmod < prottime) {
- sm = nilfs_vector_get_new_element(smv);
- if (sm == NULL) {
- nssegs = -1;
- goto out;
- }
- sm->si_segnum = segnum + i;
- sm->si_importance = imp;
+ imp = config->cf_selection_policy.p_importance(nilfs,
+ sustat, &si[i], prottime);
+
+ if (si[i].sui_lastmod < oldest)
+ oldest = si[i].sui_lastmod;
+ if (si[i].sui_lastmod < prottime) {
+ sm = nilfs_vector_get_new_element(smv);
+ if (sm == NULL) {
+ nssegs = -1;
+ goto out;
}
+ sm->si_segnum = segnum + i;
+ sm->si_importance = imp;
}
}
if (n == 0) {
@@ -642,7 +652,11 @@ nilfs_cleanerd_select_segments(struct nilfs_cleanerd *cleanerd,
break;
}
}
- nilfs_vector_sort(smv, nilfs_comp_segimp);
+ if (config->cf_selection_policy.p_comparison ==
+ NILFS_CLDCONFIG_SELECTION_POLICY_SMALLER_IS_BETTER)
+ 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;
--
1.9.0
--
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
