Re: [PATCH 2/4] nilfs-utils: add cost-benefit and greedy policies

[Andreas Rohner <andreas.rohner-hi6Y0CQ0nG0@public.gmane.org>]

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