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