Re: [PATCH v2 1/4] mm/ksm: add "smart" page scanning mode

[David Hildenbrand]

> +typedef u8 rmap_age_t;
> +
>   /**
>    * DOC: Overview
>    *
> @@ -193,6 +195,8 @@ struct ksm_stable_node {
>    * @node: rb node of this rmap_item in the unstable tree
>    * @head: pointer to stable_node heading this list in the stable tree
>    * @hlist: link into hlist of rmap_items hanging off that stable_node
> + * @age: number of scan iterations since creation
> + * @skip_age: skip rmap item until age reaches skip_age
>    */
>   struct ksm_rmap_item {
>   	struct ksm_rmap_item *rmap_list;
> @@ -212,6 +216,8 @@ struct ksm_rmap_item {
>   			struct hlist_node hlist;
>   		};
>   	};
> +	rmap_age_t age;
> +	rmap_age_t skip_age;

I *think* of you move that after "oldchecksum", the size of the struct 
might not necessarily increase.

[...]

>   
> +/*
> + * Calculate skip age for the ksm page age. The age determines how often
> + * de-duplicating has already been tried unsuccessfully. If the age is
> + * smaller, the scanning of this page is skipped for less scans.
> + *
> + * @age: rmap_item age of page
> + */
> +static unsigned int skip_age(rmap_age_t age)
> +{
> +	if (age <= 3)
> +		return 1;
> +	if (age <= 5)
> +		return 2;
> +	if (age <= 8)
> +		return 4;
> +
> +	return 8;
> +}
> +
> +/*
> + * Determines if a page should be skipped for the current scan.
> + *
> + * @page: page to check
> + * @rmap_item: associated rmap_item of page
> + */
> +static bool should_skip_rmap_item(struct page *page,
> +				  struct ksm_rmap_item *rmap_item)
> +{
> +	rmap_age_t age;
> +
> +	if (!ksm_smart_scan)
> +		return false;
> +
> +	/*
> +	 * Never skip pages that are already KSM; pages cmp_and_merge_page()
> +	 * will essentially ignore them, but we still have to process them
> +	 * properly.
> +	 */
> +	if (PageKsm(page))
> +		return false;
> +
> +	/*
> +	 * Smaller ages are not skipped, they need to get a chance to go
> +	 * through the different phases of the KSM merging.
> +	 */

Sorry, had to set some time aside to think this through. Wouldn't it be 
cleaner to just not rely on this overflow?

Instead, we could track the page age (which we would freeze at U8_MAX) 
and simply track how much more often we are allowed to skip.

Something like the following (which, I am sure, is completely broken, 
but should express what I have in mind)



age = rmap_item->age;
if (age != U8_MAX)
	rmap_item->age++;

/*
 * Smaller ages are not skipped, they need to get a chance to go
 * through the different phases of the KSM merging.
 */
if (age < 3)
	return false;

/*
 * Are we still allowed to skip? If not, then don't skip it
 * and determine how much more often we are allowed to skip next.
 */
if (!rmap_item->remaining_skips) {
	rmap_item->remaining_skips = skip_age(age);
	return false;
}

/* Skip this page. */
rmap_item->remaining_skips--;
remove_rmap_item_from_tree(rmap_item);
return true;



Would that miss anything important? Was the overflow handling (and 
scanning more often one we overflow again IIUC) important?

--
Cheers,

David / dhildenb