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