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). 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. Regards, Ryusuke Konishi -- 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
