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 <[email protected]> --- 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 [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html
