On 2014-03-16 13:55, Ryusuke Konishi wrote: > On Sun, 16 Mar 2014 11:49:16 +0100, Andreas Rohner wrote: >> 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 > > scripts/checkpatch.pl detected the following coding style issues: > > ERROR: code indent should use tabs where possible > #171: FILE: sbin/cleanerd/cldconfig.c:404: > +^I^I^I^I const struct nilfs_sustat *sustat,$ > > ERROR: code indent should use tabs where possible > #172: FILE: sbin/cleanerd/cldconfig.c:405: > +^I^I^I^I const struct nilfs_suinfo *si,$ > > ERROR: code indent should use tabs where possible > #173: FILE: sbin/cleanerd/cldconfig.c:406: > +^I^I^I^I __u64 prottime)$ > > > Please mind it next time. (You don't have to resubmit the whole series > now for this).
Normally I execute checkpatch.pl automatically via the pre-commit hook. For some reason the pre-commit hook got overwritten in my local repo. I am sorry for that. > I would like to first understand this series, but I am very busy > recently. (Also, I am still pending review of Vycheslav's xattr > patchset.) So, let me go forward a little bit at a time. Ok no problem. Regards, Andreas Rohner -- 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
